第39章：广度优先搜索进阶

挑战1：最大队列规模

对于以下无向图，列出队列中的最大项目数。假设起始顶点是A。

挑战2：迭代式BFS

在这一章中，你学习了广度优先搜索的迭代实现。现在写一个递归实现。

挑战 3：断开连接的图

给图形添加一个方法，检测图形是否断开连接。下面是一个断开连接的图的例子。

为了帮助你解决这个难题，我们在Graph协议中添加了一个属性allVertices。

var allVertices: [Vertex<Element>] { get }

这个属性已经由AdjacencyMatrix和AdjacencyList实现。

解决方案

挑战1的解决方案

队列中的最大项目数是3。

挑战2的解决方案

在广义优先搜索一章中，你学到了如何迭代地实现该算法。让我们来看看如何递归地实现它。

bfs接收源顶点以开始遍历。

1. queue记录了接下来要访问的相邻顶点。

2. enqueued记住了哪些顶点已经被添加到队列中。你可以使用一个Set来进行O(1)查找。一个数组是O(n)。

3. visited是一个数组，存储顶点被探索的顺序。

4. 通过插入源顶点来启动该算法。

5. 通过调用一个辅助函数在图上递归地执行bfs。

6. 按顺序返回所访问的顶点。这个辅助函数看起来像这样。

1. 基本情况下，递归地继续从队列中提取一个顶点，直到它为空。

2. 将顶点标记为已访问。

3. 对于来自当前顶点的每一条邻接边。

4. 在插入队列之前，检查相邻顶点是否已被访问。

5. 递归地执行bfs，直到队列为空。

广度优先搜索的总体时间复杂度为O(V+E)。

挑战3的解决方案

如果两个节点之间不存在路径，则称该图是断开的。

1. 如果没有顶点，则将该图视为连接图。

2. 从第一个顶点开始进行广度优先搜索。这个过程将返回所有被访问的节点。

3. 遍历图中的每一个顶点，检查它是否曾经被访问过。如果在访问过的集合中缺少一个顶点，那么该图就是断开的。

---

上一章	目录	下一章