Site icon Thoughts on Computing

DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS

kainwenlv
Contents hide
1 图论的术语和概念
2 深度优先搜索(Depth-first search)
3 强连通性(strong connectivity)
4 写在最后

Knuth教授的第28届圣诞讲座的视频：Stanford Lecture: Dr. Don Knuth – Strong Components and Weak Components (2024)，这引导我们继续去读一读这个Knuth教授这辈子最喜欢的算法，来自他的学生TARJAN(图灵奖得主)。

其中Knuth教授在上面的手稿里引用了一个别人对Tarjan这个算法的评论：

这更加让人想深刻理解这些科学家们的思路了。

图论的术语和概念

一个图 G 的顶点集合是V，边的集合是E。有向图的边可以表示为一个顶点的序对(v,w)，此时v称之为这有向边的尾(tail)，w称之为这条有向边的头(head)。无向图的边则没有头尾之分。G=(V, E)是一个图：

最后用一个O符号结尾这个section：f,f_1,f_2,\dots,f_n都是定义在x_1,x_2,\dots,x_n上的函数，如果满足下面条件：

\exists k_0,\dots,k_n, \forall x_1,\dots, x_n \ | f(x_1,\dots,x_n)| \le k_0 + \sum_{i=1}^{n} k_n |f_i(x_1,x_2,\dots,x_n)|

记为：f是O(f_1,\dots,f_n)。

深度优先搜索(Depth-first search)

我们先理解什么是图的搜索过程(Search of Graph G)，某个图G(V,E)

如上过程，我们称之为图的搜索(a search of graph)。

不同的搜索算法，在选择下一条去走的边使用的规则上，有较大区别。比如，定义如下规则去找下一条边：每次需要选择一条边走的时候，在最近一次才访问的顶点且它还有以它为尾(tail)的没有访问过的边集合里选择一个。这种规则的搜索，就是深度优先搜索(depth-first search)。

定义1：G=(V,E)是一个图，\forall v \in V, 构建一个顶点列表l_v = \{w| w\in V \land (v,w) \in E\}，称l_v是v的adjacency list。每一个G的顶点，所有adjacency list构成的集合，表达了图的全部信息，称之为图G的adjacency structure。

关于上面定义有一些阐述：

G是一个连通的无向图，对它进行一次搜索，每一步走一条边，这个动作会自然的赋予每条边方向。故而基于此我们可以得到一个有向图G'。这个搜索过程中，走过的每一条边，如果这些边是抵达了一个新的顶点，这些边的构成G'的生成树。如果这个搜索过程是深度优先搜索(depth-first search)，一条边(v,w)如果不在生成树里的话，那么w就是v的ancestors。

我们看一个具体的DFS过程例子，也就是论文里的FIG. 1。每一个顶点会赋予一个数字，表明它是第几个被探索的顶点，我们称这个数字为number。搜索的过程，每一条无向边虽然会存在两个顶点的adjacency list里，但只会被走一次，形成一个有向边。有时候这条有向边从number小的指向number大的，有时候反过来。看这个例子：

上面例子示意图里，最右侧的有向图，是中间搜索过程的图示化，红色的边从数字大的顶点指向数字小的。这种有向图称之为棕榈树(Palm Tree)。我们下面给出定义：

定义2：定义Palm Tree。令P(V,E)是一个有向图，它所有的边，分成两个不相交集合A, B： A \cap B = \empty , A\cup B = E, A:v \rightarrow w, B:v \small{-}\rightarrow w。如果此时还具有如下性质，就称P是棕榈树(Palm Tree)：

  1. 子图T(A)是P的生成树
  2. - \rightarrow \subseteq (\overset{*}{\rightarrow})^{-1} ，就是说每一条边(v,w)不在生成树里头的，w是v的祖先

Palm Tree和深度优先搜索(DFS)密切相关。有如下定理。

定理1：P是针对连通图G进行深度优先搜索(DFS)得到的有向图，那么P是一个棕榈树(Palm Tree)。反之亦然：如果P是一个棕榈树(Palm Tree)，那么它可以被某个DFS过程产生。

原始论文中用类似Pascal的语言展示了伪代码，我们列在下面：

BEGIN
  INTEGER i;
  PROCEDURE DFS(v, u); (* 在最终生成树结果里，u is the father of v *)
    BEGIN
      NUMBER(v) := i := i + 1;
      FOR w in adjacency list of v DO
        BEGIN
          IF w is not yet numbered THEN
            BEGIN
              construct arc v->w in P;
              DFS(w, v)
            END
          ELSE IF NUMBER(w) < NUMBER(v) and w != u THEN
            construct arc v-->w in p;
        END;
    END;
  i := 0;
  DFS(s, 0);
END;

强连通性(strong connectivity)

对有向图的搜索不会得到一个棕榈树，因为有向图里边是固定方向了。我们来看有向图的（强）连通性问题。

定义3：G(V, E)是某个有向图，如果\forall v, w \in V, \exists p_1: v \overset{*}{\Rightarrow} w \text{ and } p_2: w \overset{*}{\Rightarrow} v ，那么我们称G是强连通的。

引理：G=(V,E)是一个有向图，我们可以定义顶点集合上的等价关系：\forall v, w \in V, v \equiv w \iff \exists \text{ closed path } p: v \overset{*}{\Rightarrow} v \land w \in p。这样的等价关系对有向图G(V,E)是一个划分，每一个子图是一个强连通的，称为强连通分量。所有不同的等价类为：V_i, 1\le i \le n，令G_i=(V_i, E_i), E_i = \{(v,w) \in E | v,w \in V_i\}，则：

强连通分量在实际工程中有重要应用。这篇论文之前的算法是：从某点开始，用DFS，如果找到了一个cycle，这个cycle里的所有顶点被标记为一个等价类（强连通分量）；然后继续这个过程。这样的算法有一个缺陷：当两个小的等价类需要合并的时候，合并操作需要额外的时空复杂度。这篇论文的贡献是，发现了，不需要归并操作的，基于DFS的强连通分量发现算法，时间复杂度是O(V,E)。

上图共有8个顶点，三个强连通分量，分别用了三种颜色着色：

我们从A开始对上面的图进行DFS，扫描过程产生的丛林(Jungle)如下

引理：v和w是有向图G里属于同一个强连通分量的两个顶点。对G使用DFS搜索，得到描述搜索过程的生成森林(spanning forest)F。则\exists u, u \overset{*}{\rightarrow} v \land u \overset{*}{\rightarrow} w 。（即v,w存在公共祖先）。更进一步，如果\forall k \in \{k | k \overset{*}{\rightarrow} v \land k \overset{*}{\rightarrow} w \}, number(u) > number(k) (即u是v,w所有公共祖先里序号最大的顶点)，那么 v \overset{*}{\rightarrow} u \land w \overset{*}{\rightarrow} u （即u,v,w）属于同一强连通分量。

推论：C是有向图G里的一个强连通分量。则C的所有顶点定义了生成森林F里一个树的子树。这个子树的根(root)称之为强连通分量C的根。

故而寻找强连通分量的算法设计，一个很重要的思路就是在DFS过程中，识别每个连通分量的root。Tarjan的秘制酱料就是定义了每个顶点的LOWLINK：LOWLINK(v)是同一个连通分量内：

里先序遍历序号最小的序号值。一个重要的性质就是：

LOWLINK(v) = number(v) \iff v\text{ is root of the strong component}

深度优先搜索(DFS)的遍历的特点，我们只需要用一个stack维护看过的历史的顶点，并且动态维护LOWLINK的计算，当我们确认找到了强连通分量的顶点后，就可以从stack里抛出所有历史看过的点，只要这些点的先序序号小于当前顶点，这就是识别出来了一个强连通分量。

写在最后

本文拖延很久，最后的收尾过于仓促。很多细节的证明，还是应该一步一步的参考TAOCP里的部分会更加严格。包括弱连通分量的算法，这里也没有去看了。只能期待以后。

Exit mobile version