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

• Robert Tarjan的论文 Depth-First Search and Linear Graph Algorithms
• Knuth的TAOCP手稿 https://www-cs-faculty.stanford.edu/~knuth/fasc12a+.pdf

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

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

图论的术语和概念

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

• p: v\overset{*}{\Rightarrow}w 是图里的一条path：p=\{v_1,v_2,\dots,v_n\}, v_1,v_2,\dots,v_n \in V, v=v_1, w=v_n, \forall 1<i<n-1, (v_i, v_{i+1}) \in E。如果i\ne j \implies v_i \ne v_j，即这条path里任何顶点各不相同，就称这条path是simple的。
• 如果上面的path满足p:v\overset{*}{\Rightarrow}v ，称之为closed path。如果构成这条closed path的所有的边，各不相同，就称条path是cycle。两条 cycle_1 = \{v_1, v_2, \dots, v_{n}, v_1\}, cycle_1 = \{v^*_1, v^*_2, \dots, v^*_{n}, v^*_1\} 如果满足\{v_1,v_2,\dots,v_n\}和\{v^*_1,v^*_2,\dots,v^*_n\}互为cyclic permutations，则认为这是同一个cylce。
• 有向图可以诱导生成一个无向图：顶点集合不变，一条有向边(a,b)产生两条无向边(a,b), (b,a)，然后再对所有边进行一次去重即可。
• 如果一个无向图，\forall v_i, v_j \in E, \exists p: v_i\overset{*}{\Rightarrow}v_j ，则称一个无向图是连通的(connected)。
• Directed Root Tree的概念：
  • 是一个有向图
  • 诱导生成的无向图是connected的
  • 有且只有一个根(root, v_{root})：没有任何一条边以它为头(head), \forall v_i, v_j \in V, (v_i, v_j) \in E \implies v_j \ne v_{root}
  • 除了root以外的顶点，都满足是且仅是一条边的头：
    • \forall v \in V, v \ne v_{root} \implies \exists (v_i, v_j) \in E, v_j = v
    • \forall v \in V, v \ne v_{root} \implies ((v_i, v) \in E \land (v_j, v) \in E \implies v_i=v_j)
• T是一个Directed Root Tree，考虑顶点集合是元素集合，考虑如下的二元关系(binary relation)：
  • v\rightarrow w: (v,w) \in E ，有这么一条有向边，其中v称为father, w称为son
  • v \overset{*}{\rightarrow} w ，有一条path从v可达w，其中v称为ancestor，w称为descendant
  • > Every vertex is an ancestor and a descendant of itself.
  • v \in V, T_v(V_{T_v}, E_{T_v})是T(V_T, E_T)的子树：\forall v,w \in V_T, v \overset{*}{\rightarrow} w \iff (w \in V_{T_v} \land v \overset{*}{\rightarrow} w \text{ in } T_v)
• 生成树(spanning tree)的概念: G是一个有向图，它的一个subgraph \ T，如果包含了G的所有顶点，且T是一个有向树，可以称为生成树。
• 在讨论关系代数的一些符号 (可以参考之前的blog： https://kainwen.com/2024/12/03/complements-and-transitive-closures/)：
  • R, S都是binary relation
  • R^*是R的传递闭包(transition closure)
  • R^{-1}是R的逆(inverse)
  • 二元关系的复合操作为：RS=\{(u,w) | \exists v, (u,v)\in R \land (v,w) \in S\}

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

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

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

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

• 最开始，所有的顶点都是没有访问过的
• 从某一个顶点v开始探索过程，选择某条边(v,w) \in E顺着它就开始了，顺着它就可以到一个新的点w。相当于这条边也被走过了。
• 到了w后，我们还可以继续上面的过程。我们需要选择一个没走过的边去走。
• 选择一个没走过的边走，到达的新点，可能是访问过的，也可能是没有访问过的。
• 如果所有旧的顶点关联的边，都走过了的时候，我们需要选择一个新的从没访问过的顶点开始。
• 最终我们会探索过图的所有边，并且每条边探索且只探索了一次。

如上过程，我们称之为图的搜索(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。

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

• 对于无向图，每一条边(v,w)，会在v和w的adjacency list里都出现一次，合计两次
• 对于有向图，每一条边(v,w)，这个边只会出现在v的adjacency list里：w \in l_v
• 对于一个图，每个顶点的adjacency list，考虑其中元素顺序，也就是考虑边的顺序，实际上就可以得到不同的adjacency structure。或者我们可以说，某一个固定的图的adjacency structure，实际上对应了一种adjacency list的表的顺序

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\}，则：

• \forall i, G_i是强连通的
• 没有一个G_i是另一个连通子图的真子图

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

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

• A, B, H
• C, D, E, G
• F

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

• 上面左图实线箭头是tree arc
• 只向祖先的虚线箭头是back arc
• 既不指向祖先，也不只想后代的虚线箭头是cross arc
• 这个案例里没有forward arc和loop arc（事实上这两种arc没啥用，删除也不影响连通性）

引理：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)是同一个连通分量内：

• v
• 或者从v开始经过若干条tree arc（实线箭头），至多一个虚线箭头（back arc, cross arc）能抵达的所有顶点

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

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

写在最后

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