第41章：深度优先搜索进阶

挑战1：BFS或DFS

对于以下两个例子，哪种遍历方式（深度优先或广度优先）更有利于发现两个节点之间是否存在路径？解释一下原因。

• 从A到F的路径。

• 从A到G的路径。

挑战2：递归DFS

在本章中，你讲了深度优先搜索的迭代实现。现在写一个递归实现。

挑战3：检测循环

给Graph添加一个方法，检测一个有向图是否有循环。

解决方案

挑战1的解决方案

• 从A到F的路径：使用深度优先，因为你要找的路径在图中比较深。

• 从A到G的路径：使用宽度优先，因为你要找的路径在根附近。

挑战2的解决方案

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

1. visited记录了所访问的顶点的顺序。

2. pushed记录哪些顶点被访问过。

3. 通过调用一个辅助函数递归地执行深度优先搜索。这个辅助函数看起来像这样。

1. 将源顶点插入队列中，并将其标记为已访问。

2. 对于每条相邻的边。

3. 只要相邻的顶点还没有被访问过，就继续递归地往下潜入分支深处。

总的来说，深度优先搜索的时间复杂度是O(V+E)。

挑战3的解决方案

当一个图的边和顶点的路径回到同一个源头时，该图就有一个循环。

1. pushed是用来记录所有被访问的顶点的。

2. 通过调用一个辅助函数，递归地检查图中是否有一个循环。

这个辅助函数看起来像这样。

1. 为了启动该算法，首先插入源顶点。

2. 对于每条相邻的边。

3. 如果相邻顶点之前没有被访问过，则递归地深入到一个分支中，检查是否有循环。

4. 如果相邻的顶点以前被访问过，那么你就找到了一个循环。

5. 移除源顶点，这样你就可以继续寻找其他有潜在循环的路径。

6. 没有找到循环。

你本质上是在进行深度优先的图形遍历，通过递归潜入一条路径直到找到一个周期，然后通过弹出堆栈来回溯找到另一条路径。时间复杂度为O(V+E)。

---

上一章	目录	下一章