本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Breadth-First Search
广度优先搜索(BFS，Breadth-First Search)
这个话题已经有个辅导文章
广度优先搜索（BFS，Breadth-First Search）是用于遍历、搜索树或图数据结构的算法。它从源节点开始，在移动到下一级邻居之前首先探索直接邻居节点。
广度优先搜索可以用于有向图和无向图。
动画示例
以下是广度优先搜索在图上的工作原理：
广度优先搜索的动画示例
当我们访问节点时，将其着色为黑色。 还将其邻居节点放入队列。 在动画中，入队但尚未访问的节点以灰色显示。
让我们按照动画示例进行操作。 我们从源节点A开始，并将其添加到队列中。 在动画中，这显示为节点A变为灰色。
queue.enqueue(A)
队列现在是[A]。 我们的想法是，只要队列中有节点，我们就会访问位于队列前端的节点，如果尚未访问它们，则将其相邻的邻居节点入队。
要开始遍历图，我们将第一个节点从队列中推出A，并将其着色为黑色。 然后我们将它的两个邻居节点B和C入队。 它们的颜色变成灰色。
queue.dequeue() // A
queue.enqueue(B)
queue.enqueue(C)
队列现在是[B, C]。 我们将B出列，并将B的邻居节点D和E排入队列。
queue.dequeue() // B
queue.enqueue(D)
queue.enqueue(E)
队列现在是[C, D, E]。 将C出列，并将C的邻居节点F和G入队。
queue.dequeue() // C
queue.enqueue(F)
queue.enqueue(G)
队列现在是[D, E, F, G]。 出列D，它没有邻居节点。
queue.dequeue() // D
队列现在是[E, F, G]。 将E出列并将其单个邻居节点H排队。 注意B也是E的邻居，但我们已经访问了B，所以我们不再将它添加到队列中。
queue.dequeue() // E
queue.enqueue(H)
队列现在是[F, G, H]。 出队F，它没有未访问的邻居节点。
queue.dequeue() // F
队列现在是[G, H]。 出列G，它没有未访问的邻居节点。
queue.dequeue() // G
队列现在是[H]。 出列H，它没有未访问的邻居节点。
queue.dequeue() // H
队列现在为空，这意味着已经探索了所有节点。 探索节点的顺序是A，B，C，D，E，F，G，H。
我们可以将其显示为树：
The BFS tree
节点的父节点是"发现"该节点的节点。 树的根是广度优先搜索开始的节点。
对于未加权的图，此树定义从起始节点到树中每个其他节点的最短路径。 广度优先搜索是在图中找到两个节点之间的最短路径的一种方法。
代码
使用队列简单实现广度优先搜索：
func breadthFirstSearch(_ graph: Graph, source: Node) -> [String] {
var queue = Queue<Node>()
queue.enqueue(source)
var nodesExplored = [source.label]
source.visited = true
while let node = queue.dequeue() {
for edge in node.neighbors {
let neighborNode = edge.neighbor
if !neighborNode.visited {
queue.enqueue(neighborNode)
neighborNode.visited = true
nodesExplored.append(neighborNode.label)
}
}
}
return nodesExplored
}
虽然队列中有节点，但我们访问第一个节点，然后将其尚未被访问的直接邻居节点入队。
将此代码放在 playground中， 并进行如下测试：
let graph = Graph()
let nodeA = graph.addNode("a")
let nodeB = graph.addNode("b")
let nodeC = graph.addNode("c")
let nodeD = graph.addNode("d")
let nodeE = graph.addNode("e")
let nodeF = graph.addNode("f")
let nodeG = graph.addNode("g")
let nodeH = graph.addNode("h")
graph.addEdge(nodeA, neighbor: nodeB)
graph.addEdge(nodeA, neighbor: nodeC)
graph.addEdge(nodeB, neighbor: nodeD)
graph.addEdge(nodeB, neighbor: nodeE)
graph.addEdge(nodeC, neighbor: nodeF)
graph.addEdge(nodeC, neighbor: nodeG)
graph.addEdge(nodeE, neighbor: nodeH)
graph.addEdge(nodeE, neighbor: nodeF)
graph.addEdge(nodeF, neighbor: nodeG)
let nodesExplored = breadthFirstSearch(graph, source: nodeA)
print(nodesExplored)
结果输出： ["a", "b", "c", "d", "e", "f", "g", "h"]
BFS有什么用？
广度优先搜索可用于解决许多问题。 例如：
作者：Chris Pilcher， Matthijs Hollemans
翻译：Andy Ron
校对：Andy Ron
网友评论