深度优先搜索的赞歌

在处理图结构时，一个基本需求是能够搜索或处理图中的所有顶点。这可能是为了查找存储在某个或某些节点上的信息，也可能是为了通过给图的所有顶点进行二着色来判断图是否为二分图；又或者，我们可能需要编写一个算法来遍历以图形式表示的迷宫。深度优先搜索（DFS）正是解决这类问题的经典算法。

深度优先搜索在我们的编程心中占据着特殊地位，它作为子程序被广泛应用于众多其他图算法中。本章我们将看到一些这样的算法。

基本思想

DFS的核心思想是从某个顶点出发，移动到一个尚未访问过的相邻顶点。我们持续这样前进，直到在一个节点 $v^\prime$ 处陷入僵局——即该节点的所有邻居都已被访问过。此时我们将 $v^\prime$ 视为已探索，并从之前访问它的那个节点回溯，也就是“退回到”最初到达 $v^\prime$ 的那个顶点。然后我们可以再次继续深入探测，直到再次需要回溯。这种遍历图的方法被称为深度优先搜索。

另一方面，如果图是不连通的，搜索必须从每个连通分量重新开始。在这种情况下，已探索的顶点和边可以被看作是一片森林，其中每棵树对应一个连通分量。这种森林被称为深度优先森林。

实现细节

我们定义一个函数 DepthFirstSearch 来实现对输入图的深度优先搜索。该函数完成一些初始化工作，并使用子程序 DiveDeep 来协助搜索过程。

对于每个顶点 $v$，我们定义以下属性：

1. $v.visited$：取布尔值 true 或 false。
2. $v.parent$：指向该顶点在深度优先树中父节点的指针。

• 第2–4行：我们将所有顶点初始化为未访问状态，并将它们的父指针设为 nil。

• 第5–7行：我们通过调用子程序 DiveDeep 从一个未访问的顶点开始实际搜索。这个循环确保，如果一次对 DiveDeep 的调用未能访问图中所有顶点，搜索将在下一轮从一个尚未访问的顶点重新启动。这种情况发生在输入图不是连通图时。

当一个顶点被 DiveDeep 子程序访问时，它会在第2行被标记为已访问。接着，在第3–6行，我们逐个探索其所有关联边。如果某条边的另一端连接的是一个未访问的顶点，那么该顶点将成为当前顶点的子节点，并从该子节点递归地继续搜索。

运行时间

DepthFirstSearch 的运行时间为 $O(n+m)$，其中 $n$ 是顶点数，$m$ 是边数。下面我们分析原因。

我们通过累加每行代码所花费的时间来进行运行时间分析。由于部分代码是递归调用，我们需要考虑在整个程序执行过程中这些调用的总成本。

对于 DepthFirstSearch 函数：

• 第一个循环 （第2–4行） 花费 $O(n)$ 时间，因为它执行 $n$ 次，且每次循环体包含常数时间的操作。
• 如果忽略对 DiveDeep 的调用，第二个循环 （第5–7行） 也花费 $O(n)$ 时间。

因此，总运行时间为 $O(n)$ 加上所有 DiveDeep 调用所花费的时间。接下来我们分析以下两部分耗时：

1. 调用 DiveDeep 的总时间
2. 所有 DiveDeep 调用内部的总时间

我们将这两部分相加，得到总的运行时间。

• 针对第1点：DiveDeep 每个未访问的顶点恰好被调用一次，无论是由 DepthFirstSearch 直接调用，还是在 DiveDeep 内部递归调用。这意味着在整个 DepthFirstSearch 执行过程中，总共会有 $n$ 次对 DiveDeep 的调用。

• 针对第2点：我们来看 DiveDeep 中每行代码的执行时间：

  • 单次执行 第2行 为 $O(1)$。由于 DiveDeep 被调用了 $n$ 次，该行总共耗时 $O(n)$。
  • 而 第3行 的循环，每个顶点只执行一次，迭代次数等于该顶点的出边数量。因此在整个递归执行过程中，第3行 总共被执行 $O(m)$ 次。
  • 由于 第3行 是 $O(m)$，所以 第4–5行 也是 $O(m)$。

将所有这些成本相加，总运行时间为 $O(n + m)$。

深度优先搜索也可用于有向图

该算法同样适用于有向图，只要我们在探索时仅允许沿着顶点的出边前进即可。

我们可以将 DepthFirstSearch 的实现应用于以下有向图。注意，此时生成的是深度优先森林而非单一的深度优先树。此外，我们还可以按照以下说明修改该有向图：