跳转至

38.广度优先搜索

在上一章中，你探索了使用图形来捕捉对象之间的关系。请记住，对象只是顶点，而边代表它们之间的关系。

有几种算法可以遍历或搜索图的顶点。其中一种算法是breadth-first search (BFS)算法。

BFS可以用来解决各种各样的问题：

  1. 生成一个最小跨度的树。
  2. 寻找顶点之间的潜在路径。
  3. 找到两个顶点之间的最短路径。

示例

BFS从选择图中的任何顶点开始。然后，该算法在遍历该顶点的邻居之前，会探索该顶点的所有邻居，以此类推。顾名思义，这种算法采取breadth-first的方法。

通过一个BFS的例子，使用以下无向图：

img

Note

突出显示的顶点代表已访问的顶点。

你将使用一个queue来记录下一个要访问的顶点。队列的first-in-first-out方法保证了在你越过一个层次之前，所有顶点的邻居都被访问过。

img

  1. 开始时，你选择一个源顶点来开始。这里，你选择了A，它被添加到队列中。
  2. 只要队列不是空的，你就取消队列并访问下一个顶点，在本例中是A。接下来，你把A的所有相邻顶点[B, D, C]加入队列。

Note

需要注意的是，只有当一个顶点还没有被访问过并且还没有在队列中时，你才会将其加入队列。

img

  1. 队列不是空的，所以你取消队列并访问下一个顶点，B。然后你把B的邻居E添加到队列中。A已经被访问了，所以它没有被添加。现在队列中有[D, C, E]。
  2. 下一个要排队的顶点是D。D没有任何未被访问的邻居。现在队列中有[C, E]。

img

  1. 接下来，你把C去掉，把它的邻居[F, G]加入队列。现在队列中有[E, F, G]。

Note

你现在已经访问了A的所有邻居! BFS现在转到第二层邻居。

  1. 你把E去掉，把H添加到队列中。现在队列中有[F, G, H]。你不把B或F加入队列，因为B已经被访问，F已经在队列中。

img

  1. 你把F去掉，由于它所有的邻居都已经在队列中或被访问过，你不需要向队列中添加任何东西。
  2. 和上一步一样，你删除G，并且不向队列中添加任何东西。

img

  1. 最后，你把H去掉。由于队列现在是空的，所以广度优先搜索已经完成了
  2. 在探索顶点时，你可以构建一个树状结构，显示每一级的顶点：首先是你开始的顶点，然后是它的邻居，然后是它邻居的邻居，以此类推。

实施

打开本章的启动playground。这个playground包含了你在上一章中构建的图形的实现。它还包括一个基于栈的队列实现，你将用它来实现BFS。

在你的主playground文件中，你会注意到一个预先建立的样本图。添加下面的代码：

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
  }
}

在这里，你定义了一个方法breadthFirstSearch(from:)，它接收了一个起始顶点。它使用了三个数据结构：

  1. queue记录下一步要访问的相邻顶点。
  2. enqueued记住哪些顶点以前被排过队，所以你不会对同一个顶点排队两次。你在这里使用一个Set类型，所以查找很便宜，只需要O(1)。
  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顶点来启动BFS算法。
  2. 你继续从队列中提取顶点，直到队列为空。
  3. 每当你从队列中提取一个顶点，你就把它加入到访问顶点的列表中。
  4. 然后，你找到所有从当前顶点开始的边，并对它们进行迭代。
  5. 对于每条边，你检查它的目标顶点是否已经被排队，如果没有，你就把它添加到代码中。

这就是实现BFS的全部内容! 让我们给这个算法来个旋转。添加以下代码：

let vertices = graph.breadthFirstSearch(from: a)
vertices.forEach { vertex in
  print(vertex)
}

注意使用BFS探索的顶点的顺序：

0: A
1: B
2: C
3: D
4: E
5: F
6: G
7: H

对于相邻的顶点要记住的一点是，你访问它们的顺序是由你构建图形的方式决定的。你可以在A和C之间添加一条边，然后再在A和B之间添加一条。在这种情况下，输出将在B之前列出C。

性能

当使用BFS遍历一个图形时，每个顶点都被排队一次。这个过程的时间复杂度为O(V)。在这个遍历过程中，你还要访问所有的边。访问所有边的时间是O(E)。将两者相加意味着广度优先搜索的总体时间复杂度为O(V + E)。

BFS的空间复杂度是O(V)，因为你必须将顶点存储在三个独立的结构中：queue，enqueued和visited。

关键点

  • 广度优先搜索（BFS）是一种用于遍历或搜索图形的算法。
  • BFS在遍历下一层顶点之前，会探索当前顶点的所有邻居。
  • 一般来说，当你的图结构有许多相邻的顶点或者你需要找出每一个可能的结果时，使用这种算法是很好的。
  • 队列数据结构被用来优先遍历一个顶点的边，然后再向下深入一层。