Fork me on GitHub

【译】Swift算法俱乐部-广度优先搜索

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.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变为灰色。

1
queue.enqueue(A)

队列现在是[A]。 我们的想法是,只要队列中有节点,我们就会访问位于队列前端的节点,如果尚未访问它们,则将其相邻的邻居节点入队。

要开始遍历图,我们将第一个节点从队列中推出A,并将其着色为黑色。 然后我们将它的两个邻居节点BC入队。 它们的颜色变成灰色。

1
2
3
queue.dequeue()   // A
queue.enqueue(B)
queue.enqueue(C)

队列现在是[B, C]。 我们将B出列,并将B的邻居节点DE排入队列。

1
2
3
queue.dequeue()   // B
queue.enqueue(D)
queue.enqueue(E)

队列现在是[C, D, E]。 将C出列,并将C的邻居节点FG入队。

1
2
3
queue.dequeue()   // C
queue.enqueue(F)
queue.enqueue(G)

队列现在是[D, E, F, G]。 出列D,它没有邻居节点。

1
queue.dequeue()   // D

队列现在是[E, F, G]。 将E出列并将其单个邻居节点H排队。 注意B也是E的邻居,但我们已经访问了B,所以我们不再将它添加到队列中。

1
2
queue.dequeue()   // E
queue.enqueue(H)

队列现在是[F, G, H]。 出队F,它没有未访问的邻居节点。

1
queue.dequeue()   // F

队列现在是[G, H]。 出列G,它没有未访问的邻居节点。

1
queue.dequeue()   // G

队列现在是[H]。 出列H,它没有未访问的邻居节点。

1
queue.dequeue()   // H

队列现在为空,这意味着已经探索了所有节点。 探索节点的顺序是ABCDEFGH

我们可以将其显示为树:

The BFS tree

节点的父节点是”发现”该节点的节点。 树的根是广度优先搜索开始的节点。

对于未加权的图,此树定义从起始节点到树中每个其他节点的最短路径。 广度优先搜索是在图中找到两个节点之间的最短路径的一种方法。

代码

使用队列简单实现广度优先搜索:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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中, 并进行如下测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

坚持原创技术分享,您的支持将鼓励我继续创作!