广度优先搜索和深度优先搜索是在图的基础上来讨论的，它们都是图的顶点的遍历方式。下面我们一个个来研究一下。
两种遍历方式的讲解，我们都已下面这个图为例：
构建这个图的代码如下：
let graph = AdjacencyList<String>()
let a = graph.createVertex(value: "A")
let b = graph.createVertex(value: "B")
let c = graph.createVertex(value: "C")
let d = graph.createVertex(value: "D")
let e = graph.createVertex(value: "E")
let f = graph.createVertex(value: "F")
let g = graph.createVertex(value: "G")
let h = graph.createVertex(value: "H")
graph.addUndirectedEdge(between: a, and: b, weight: nil)
graph.addUndirectedEdge(between: a, and: c, weight: nil)
graph.addUndirectedEdge(between: b, and: d, weight: nil)
graph.addUndirectedEdge(between: c, and: e, weight: nil)
graph.addUndirectedEdge(between: c, and: f, weight: nil)
graph.addUndirectedEdge(between: d, and: e, weight: nil)
graph.addUndirectedEdge(between: e, and: f, weight: nil)
graph.addUndirectedEdge(between: d, and: g, weight: nil)
graph.addUndirectedEdge(between: e, and: h, weight: nil)
graph.addUndirectedEdge(between: f, and: h, weight: nil)
广度优先搜索
广度优先搜索可以用来解决这些问题：1）生成最小生成树；2）寻找顶点之间所有可能的路径；3）寻找顶点之间的最短路径。
我们把从一个起点开始的边的终点称为邻居，那么广度优先搜索的执行过程可以概括为：首先选择一个起点，然后遍历完这个起点的所有邻居之后再遍历这些邻居的邻居，以此类推。
我们将使用队列来存储要遍历的顶点，队列先进先出的特性可以保证一个顶点的邻居在邻居的邻居之前遍历。下面我们一步步来演示遍历的过程。
- 起点是 A，首先遍历的是 A，把 A 放到队列中，状态如下：
- 只要队列不是空的，我们就拿出一个元素，然后遍历下一个元素。这里我们拿出 A，然后把 A 的邻居加入队列中，状态如下：
- 把 B 拿出，然后再把 B 的邻居 D 加入队列中，邻居 A 已经遍历过了，不需要再加入。状态如下：
- 把 C 拿出，然后把邻居 E 和 F 加入队列中，邻居 A 已经遍历过了，不需要再加入。状态如下：
- 把 D 拿出，然后把邻居 G 加入队列中，邻居 B 已经遍历过了，邻居 E 已经在队列中，不需要再加入。状态如下：
- 把 E 拿出，然后把邻居 H 加入队列中，邻居 C 已经遍历过了，邻居 F 已经在队列中，不需要再加入。状态如下：
- 把 F 拿出，邻居 C 和 E 已经遍历过了，邻居 H 已经在队列中，不需要再加入。状态如下：
- 把 G 拿出，邻居 D 已经遍历过了，不需要再加入。状态如下：
- 最后把 G 拿出，邻居 E 和 F 已经遍历过了，不需要再加入。状态如下：
代码实现
代码实现如下：
extension Graph {
func breathFirstSearch(from source: Vertex<Element>) -> [Vertex<Element>] {
// 存储即将遍历的顶点
var queue = Queue<Vertex<Element>>()
// 存储已经入队的顶点
var enqueued: Set<Vertex<Element>> = []
// 存储已经遍历的顶点
var visited: [Vertex<Element>] = []
queue.enqueue(source)
enqueued.insert(source)
while let vertex = queue.dequeue() { // 取出队列的顶点
visited.append(vertex)
let neighborEdges = edges(from: vertex)
for edge in neighborEdges
where !enqueued.contains(edge.destination) {
// 把没有入队的邻居加入队列中
queue.enqueue(edge.destination)
enqueued.insert(edge.destination)
}
}
return visited
}
}
测试
let vertices = graph.breathFirstSearch(from: a)
vertices.forEach { print($0) }
// 结果
0: A
1: B
2: C
3: D
4: E
5: F
6: G
7: H
如果要使用 AdjacencyMatrix，添加边的时候 weight 必须要有值。
性能分析
在遍历过程中，每个顶点入队一次，时间复杂度为 O(V)，在遍历过程中，我们还遍历了所有的边，时间复杂度为 O(E)，所以总体的事件复杂度为 O(V + E)。
深度优先搜索
深优先搜索可以用来解决这些问题：1）拓扑排序；2）检测是有循环；3）寻找路径；4）在图中寻找连通的组件。
深度优先搜索的执行过程可以概括为：从一个顶点开始，尽可能的往下搜寻，直到到达底部为止；然后在往回走，搜寻另外一个分支，直到遍历完整个图。
我们将使用栈来存储要遍历的顶点，队列后进先出的特性可以让我们在一个分支走到底部时往回走。每次 push 一个顶点，就意味着往更深一层。下面我们一步步来演示遍历的过程。
- 以 A 为起点，首先把 A push 到栈中，状态如下：
- 只要栈不为空，就查看栈顶的顶点，然后栈顶顶点的第一个邻居 push 到栈上，也即是 B 入栈，状态如下：
- 现在栈顶顶点为 B，第一个邻居为 D，所以把 D push 到栈中，状态如下：
- 现在栈顶顶点为 D，第一个邻居为 E，所以把 E 入栈，状态如下：
- 现在栈顶顶点为 E，第一个邻居为 C，所以把 C 入栈，状态如下：
- 现在栈顶顶点为 C，它的两个邻居 A 和 E，都已在栈中，所以把第三个邻居 F 入栈，状态如下：
- 现在栈顶顶点为 F，邻居 E 已经在栈中，所以把 H 入栈，状态如下：
- 现在栈顶顶点为 H，他已经没有其他邻居，到达了底部，所以把它从栈顶中取出，状态如下：
- 接下来的三个栈顶顶点 F、C 和 E，都没有其他邻居，都要被取出。取出后状态如下：
- 栈顶顶点 D 还有另外一个邻居 G 没有遍历，所以把 G 入栈，状态如下：
- 栈顶顶点 G，没有其他邻居，把 G 取出。状态如下：
- 接下来的三个栈顶顶点 D、B 和 A，都没有其他邻居，都要被取出。取出后遍历完成。
代码实现
extension Graph {
func depthFirstSearch(from source: Vertex<Element>) -> [Vertex<Element>] {
// 存储即将遍历的顶点
var stack = Stack<Vertex<Element>>()
// 存储已经入栈的顶点
var pushed: Set<Vertex<Element>> = []
// 存储已经遍历过的顶点
var visited: [Vertex<Element>] = []
stack.push(source)
pushed.insert(source)
visited.append(source)
outer: while let vertex = stack.top { // 判断栈顶的顶点是否为空
let neighborEdges = edges(from: vertex)
guard !neighborEdges.isEmpty else {
// 如果当前顶点没有邻居，把栈顶顶点取出
stack.pop()
continue
}
for edge in neighborEdges {
if !pushed.contains(edge.destination) { // 当前顶点的邻居没遍历过
stack.push(edge.destination)
pushed.insert(edge.destination)
visited.append(edge.destination)
// 继续执行外部的 while 循环，尝试往更深的一层继续遍历
continue outer
}
}
// 没有其他没有遍历过的邻居，把栈顶顶点取出
stack.pop()
}
return visited
}
}
测试
let vertices = graph.depthFirstSearch(from: a)
vertices.forEach { print($0) }
// 结果
0: A
1: B
3: D
4: E
2: C
5: F
7: H
6: G
性能分析
在遍历过程中，每个顶点都会被遍历一次，时间复杂度为 O(V)，在遍历过程中，我们还遍历了所有的邻居，以确定是否还要继续往更深一层继续遍历，时间复杂度为 O(E)，所以总体的事件复杂度为 O(V + E)。空间复杂度为 O(V)，因为我们要存储图中的所有顶点。
完整代码 >>
参考资料
Data Structures and Algorithms in Swift --- raywenderlich.com，如果想看原版书籍，请点击链接购买。
