【图论算法】深度优先搜索的应用

深度优先搜索(depth-first search)是对先序遍历(preorder traversal)的推广。我们从某个顶点 v 开始处理 v，然后递归地遍历所有邻接到 v 的顶点。

对一棵树的所有顶点的访问需 O(|E|) 时间。对任意图进行该过程时则需要考虑避免圈的出现。为此，当访问一个顶点 v 的时候，由于当时已经到了该点处，因此可以标记该点是访问过的，并且对于尚未被标记的所有邻接顶点递归调用深度优先搜索。该方法保证每条边只访问一次，所以只要使用邻接表，则执行遍历的总时间就是 O(|E|+|V|)。

无向图是连通的，当且仅当从任一节点开始的深度优先搜索访问到每一个节点。 我们以图形来描述深度优先生成树(depth-first spanning tree) 的步骤。该树的根为 A，是第一个被访问的节点。图中每条边 (v, w) 都出现在树上。如果当处理 (v, w) 时发现 w 是未被标记的，就用树的一条边来表示它。如果其已被标记，则画一条虚线，并称之为背向边 (back edge)，表示这条 ‘边’ 实际上不是树的一部分。对图1 中的无向图进行 dfs 得到的深度优先生成树 如图2 所示。 只使用树的边对该树的先序编号 (preorder numbering) 告诉我们这些顶点被标记的顺序。如果图不是连通的，那么处理所有的节点（和边）则需要多次调用 dfs，每次生成一棵树，整个集合就是深度优先生成森林(depth-first spanning forest)。

一个连通的无向图，如果不存在这样的顶点，即使得该顶点被删除之后剩下的图不再连通，那么这样的无向连通图就称为双连通(biconnected) 的。 上例中的图1 中的无向图就是双连通的。

如果一个图不是双连通的，那么，将其删除使图不再连通的那些顶点叫作割点(articulation point)。 这些节点在许多应用中很重要。图3 不是双连通的：顶点C 和 D 是割点。

深度优先搜索提供一种找出连通图中的所有割点的线性时间算法。首先，从图中任一顶点开始，执行深度优先搜索并在顶点被访问时给它们编号。对于每一个顶点 v，我们称其先序编号(preorder number) 为 Num(v)。然后，对于深度优先搜索生成树上的每一个顶点 v，计算编号最低的点，我们称之为 Low(v)，该点可从 v 开始通过树的零条或多条边，且可能还有一条背向边而达到。

从A、B 和 C 开始的可达到最低编号顶点为顶点1（A），因为它们都能通过树的边到 D，然后再由一条背向边回到 A。可以通过对该深度优先生成树执行一次后序遍历有效地计算 Low。根据 Low 的定义可知 Low(v) 是下列各项中的最小者：

图4 中的深度优先搜索树首先显示先序编号，然后指出在上述法则下可达到的最低编号节点。 Low(v) 的计算：扫描 v 的邻接表，应用适当的法则，并记住最小者。所有的计算花费 O(|E|+|V|) 时间。

剩下的就是利用这些信息找出所有的节点。根是割点当且仅当它有多于一个的儿子，因为如果它有两个儿子，那么删除根则使得不同子树上的节点不连通；如果根只有一个儿子，那么除去该根只不过断离该根。对于任何其他顶点 v，它是割点当且仅当 v 有某个儿子 w 使得 Low(w) ≥ Num(v)。 在图4 中，D有一个儿子 E，且 Low(E) ≥ Num(D)，二者都是4，对 E 来说只有一种方法到达 D 上面的任何一点，那就是通过 D。类似的，C 也是一个割点，因为 Low(G) ≥ Num©。

最后，给出该算法实现的伪代码。设 Vertex 包含数据成员 visited（初始化为false）、num、low 和 parent。为给先序遍历编号 num 赋值，还要有一个(Graph)类变量 counter，其初始化为 1。该算法可以通过执行一次先序遍历计算 Num，而后再执行一趟后序遍历计算 Low 来实现。

对顶点的 Num 赋值的例程：

计算 Low 并检验是否割点的伪代码：