【译】数据结构与算法——广度优先搜索

发表于 分类于

广度优先搜索（BFS）是对树 或 图等数据结构进行遍历或搜索时应用的一种算法。它从起始节点开始，先遍历最近的节点，之后在遍历下一级的临近节点。

广度优先搜索即可用于有向图也可用于无向图。

动画示例

下面的动画展示了广度优先算法是如何搜索一个图的：

Animated example of a breadth-first search

当访问一个节点时，将其标黑。同时将它的临近节点放入队列中。那些已入队但尚未被访问的节点，在动画中以灰色标记。

让我们跟着动画（来熟悉一下过程），首先从起始节点 A 开始，将其添加到队列中，此时 A 节点变成灰色。

1
queue.enqueue(A)

队列变成 [ A ]。（之后的）思路是，随着节点的入队，在访问位于队首的节点的同时，将其尚未被访问的临近节点入队，（以此类推，如此往复）。

在开始遍历图之前，先将起始节点 A 出队，并将其标黑。紧接着入队它的两个临近节点 B 和 C，与此同时将他们标灰。

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

此时队列变为 [ B, C ]。接着将 B 出队，在将 B 的临近节点 D 和 E 入队。

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

这时队列变为 [ C, D, E ]。之后将 C 出队，并将 C 的临近节点 F 和 G 入队。

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 的临近节点，但是由于已经被访问过，所以不再重复入队。

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

至此，队列为空，这意味着所有的节点都已经被遍历过。各节点遍历的顺序依次为 A, B, C, D, E, F, G, H。

以树来表示形式如下：

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适用哪些场景呢？

广度优先算法适用范围很广，下面举两个简单的应用：

最后

该系列文章翻译自 Raywenderlich 的开源项目：swift-algorithm-club，意在帮助有一定基础的同学进行回顾，如果你才接触，那么建议移步详细教程

Written by Chris Pilcher and Matthijs Hollemans

由 William Han 翻译