在之前的文章中，我们了解到如何使用图来表达对象之间的关系。需要铭记的是对象是用顶点(vertices)表示，对象之间的关系是使用边（edge）表示。
bread-first search(BFS)算法是遍历图的一种算法，BFS可以解决很多问题，例如：
1，生成最小生成树。
2，找到顶点之间的潜在路径
3，找到两个顶点之间的最短路径。
示例
BFS是从图的任意一个顶点开始，然后访问它们所有的邻居顶点，重复以上操作，直到遍历完所有顶点。
我们通过以下无向图来探索BFS算法：
BFS1.png
高亮的顶点表示已经访问过的顶点
我们将使用 队列(queue)来记录顶点的访问顺序，队列FIFO的特性保证了我们在遍历的时候，先遍历其邻居，然后在遍历更深的一层。
BFS2.png
1，一开始，选择A作为起点，并且将它加入到 queue中，
2，由于队列不是空的，让队列出队，此时该值为 A，并且访问A，接下来，将A的所有邻居[B，D，C]入队。
⚠️⚠️⚠️当使顶点入队时，必须是还没访问过的顶点，并且不在队列中
BFS3.png
1，当 queue 非空时，将B顶点出队，并且访问B顶点，接下来，将B的邻居 [E]入队。因为 A已经访问过了，不需要再次将A入队，现在 队列里面的元素是 [D, C, E]。
2，下一个需要出队的顶点是D。D没有任何没有访问过的邻居，没有新顶点入队。当前队列里面的元素是 [C, E]。
BFS4.png
1，接下来，将C出队，并且将它们的邻居 [F，G]入队，现在队列里面的元素为 [E, F, G]。
到目前为止，我们已经访问了A的所有邻居！BFS算法开始访问第二层元素了。
BFS5.png
重复上面的操作，将G出队，没有新顶点元素入队。
1，将E出队，并访问，将E未访问过的的邻居H入队。现在队列里面的元素为 [F, G, H]。
2，将 F 出队，因为 E 和 C 已经访问过，G已经在当前队列中，所以没有新的顶点元素入队。
BFS6.png
1，最后，将 H 出队，由于现在队列里面已经没有元素了，BFS遍历结束。
2，在对顶点进行遍历时，遍历的元素按顺序可以重建一个类似于树的一种结构。结果和 二叉树的层级遍历一致。
实现
我们给图增加一个扩展：
extension Graph where Element: Hashable {
func breadthFirstSearch(from source: Vertex<Element>)
-> [Vertex<Element>] {
var queue = QueueStack<Vertex<Element>>()
var enqueued: Set<Vertex<Element>> = []
var visited: [Vertex<Element>] = []
// more to come
return visited
}
}
source为我们遍历图的起点，在这里我们使用了三种数据结构：
1，queue 用来记录接下来要访问的顶点。
2，enqueued 用来记录已访问的顶点，避免同一个顶点访问多次。我们使用 Set。
3，visited 是一个数组，用来有序的存储已访问的元素。
接下来，我们来完善该实现：
queue.enqueue(source) // 1
enqueued.insert(source)
while let vertex = queue.dequeue() { // 2
visited.append(vertex) // 3
let neighborEdges = edges(from: vertex) // 4
neighborEdges.forEach { edge in
if !enqueued.contains(edge.destination) { // 5
queue.enqueue(edge.destination)
enqueued.insert(edge.destination)
}
}
}
1，在一开始，将 source 顶点入队。
2，将队列里面的元素出队，直到队列元素为空。
3，每当将元素出队时，将它将它加到有序数组中。
4，将出队元素的所有边进行遍历。
5，将出队元素没有访问过的顶点入队。
以上就是 BFS的全部了，我们来测试一下
let vertices = graph.breadthFirstSearch(from: a)
vertices.forEach { vertex in
print(vertex)
}
我们看下输出打印结果：
0: A
1: B
2: C
3: D
4: E
5: F
6: G
7: H
最后附上本文的相关代码DataAndAlgorim
网友评论