第38章：广度优先搜索

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

有几种算法可以遍历或搜索图的顶点。其中一种算法是广度优先搜索（BFS）算法。

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

1. 生成一棵最小跨度的树。

2. 寻找顶点之间的潜在路径。

3. 找到两个顶点之间的最短路径。

例子

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

通过一个BFS的例子，使用下面的无向图。

注：突出显示的顶点代表被访问的顶点。

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

1. 开始时，你选择一个源顶点来开始。这里，你选择了A，它被添加到队列中。

2. 只要队列不是空的，你就取消队列并访问下一个顶点，在本例中是A。

注意：重要的是要注意，只有当一个顶点还没有被访问过，并且不在队列中时，你才会把它添加到队列中。

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

4. 下一个要去排队的顶点是D，D没有任何未被访问的邻居。现在队列中有[C, E]。

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

请注意，你现在已经访问了A的所有邻居！BFS现在进入第二步。BFS现在转到第二层邻居。

6. 你删除E并将H加入队列中。现在队列中有[F, G, H]。你不把B或F加入队列，因为B已经被访问了，F也已经在队列中了。

7. 你取消对F的排队，因为它的所有邻居都已经在队列中或被访问过，所以你不向队列中添加任何东西。

8. 像上一步一样，你把G去掉，不向队列中添加任何东西。
   

9. 广度优先搜索完成了，因为队列现在是空的！

10. 在探索顶点时，你可以构建一个树状结构，显示每一级的顶点：首先是你开始的顶点，然后是它的邻居，然后是它邻居的邻居，以此类推。

实现

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

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

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

1. queue记录下一步要访问的相邻顶点。

2. enqueued记住了哪些顶点以前被排过队，所以你不会对同一个顶点排队两次。你在这里使用一个Set类型，这样查找起来就很便宜，只需要O(1)。

3. visited是一个数组，存储顶点被探索的顺序。接下来，通过替换注释来完成该方法。

下面是发生的事情。

1. 你首先通过排队等待源顶点来启动BFS算法。

2. 你继续从队列中提取顶点，直到队列为空。

3. 每当你从队列中提取一个顶点，你就把它加入到访问顶点的列表中。

4. 然后，你找到所有从当前顶点开始的边，并对它们进行迭代。

5. 对于每条边，你检查它的目标顶点是否已经被排队，如果没有，你就把它添加到代码中。

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

请注意使用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)，因为你必须将顶点存储在三个独立的结构中：队列、排队和访问。

关键点

• 广度优先搜索（BFS）是一种用于遍历或搜索图形的算法。

• BFS在遍历下一级顶点之前，会探索当前顶点的所有邻居。

• 一般来说，当你的图结构有很多相邻的顶点或者你需要找出每个可能的结果时，使用这种算法是很好的。

• 队列数据结构被用来优先遍历一个顶点的边，然后再向下深入一层。

---

上一章	目录	下一章