最强连通分量（Tarjan）笔记

2023-11-05 10:25:46

引言

在静态分析技术中, 我们常用会将代码转成抽象语法树(AST), 然后采用深度遍历（DFS）来完成对语法树的遍历和查询，找到潜在的问题缺陷。

对于语义的分析，我们采用的控制流和数据流也都无一例外的采用了以图为基础的算法, 通过图的可达性, 来完成变量、表达式的可达分析, 以及变量的依赖分析、值流图等等。

图的算法是进行静态分析的基础数据算法，如何提高图的分析效率，就需要对图的算法有进一步的认识。

Tarjan算法

图的一些基本概念：

关联（incident）：点为边的端点;
邻接（adjacent）：点与点关联同一条边，或边与边关联同一顶点；
子图：图G'的点和边都是图G的子集，则G'为G的子图;
道路：从点v到点u的路径；
简单道路：没有重复边的道路；
回路：起点与终点相同的道路；
简单回路：没有重复边的回路；
连通：两顶点间有道路；
强连通：有向图u→v与v→u都有道路；
连通图：任意两顶点间都有道路（若有向图除去方向后连通，则称有向图连通）；
简单图：没有重复边和自环的图；
完全图：任意两顶点间有一条边到达的简单图（有向完全图与无向完全图）；
强连通（strongly connected）: 在有向图G 中，如果两个顶点间至少存在一条路径，称两个顶点强连通（strongly connected）；
强连通图: 如果有向图G 的每两个顶点都强连通，称G 是一个强连通图；
强连通分量(strongly connected components): 非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

求强连通分量就是我们今天要解决的问题，根据强连通分量定义，用双向遍历取交集的方法求强连通分量，时间复杂度为 \(\Theta(N^2+M)\). 而Tarjan或Kosaraju算法, 两者的时间复杂度都是 \(\Theta(N+M)\)。

算法简介

Tarjan 算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义:
- DFN(u)为节点u 搜索的次序编号(时间戳);
- LOW(u)为u 或 u的子树能够追溯到的最早的栈中节点的次序号;
  由定义可以得出，当 DFN(u)=LOW(u)时，以u为根的搜索子树上所有节点是一个强连通分量。
算法：
1.当首次搜索到点u时DFN[u]=LOW[u]=time;
2.每当搜索到一个点，把该点压入栈顶;
3.当u和v有边相连时:
（1）如果v不在栈中（树枝边），DFS(v)，并且LOW[u] = min{LOW(u),LOW(v)};
（2）如果v在栈中（前向边/后向边），此时LOW[u] = min{LOW[u],DFN[v]}
- 当DFN[u]=LOW[u]时，将它以及在它之上的元素弹出栈，此时，弹出栈的结点构成一个强连通分量;
- 继续搜索，知道图被遍历完毕。

由于在这个过程中每个点只被访问一次，每条边也只被访问一次，所以Tarjan算法的时间复杂度是 \(\Theta(n + m)\).

tarjan(u) {
    DFN[u] = LOW[u] = ++Index            //为节点u设定次序编号和Low初值
    Stack.push(u)                        //将节点u压入栈中
    for each(u, v) in E                  //枚举每一条边 
        if(v is not visted)              //如果节点v未被访问过 
            tarjan(v)                    //继续向下找 
            LOW[u] = min(LOW[u], LOW[v]) //
        else if(v in Stack)              //如果节点v还在栈内 
            LOW[u] = min(LOW[u], DFN[v]) //
    if(DFN[u] == LOW[u])                 //如果节点u是强连通分量的根 
        repeat                           //循环出栈，直到u=v 
            v = Stack.pop                //将v退栈，为该强连通分量中的一个顶点 
            print v                      //输出v 
        until(u == v)                    //循环终止条件u=v 
}

举例演算

0.求下面有向图的强连通分量

1.从节点0开始DFS:

代码(1)-(5): 得到访问链:0 -> 2 -> 4 -> 5, 把遍历到的4个节点{0, 2, 4, 5}加入栈中; 四个节点的LOW[] 和 DFN[]值, 依次被Index标注成1到4; 注: 这里也可以走另外一条路径: 0 -> 2 -> 3 -> 5;
代码(9)-(13): 节点5的后续边已经遍历完成, 退出节点5时, 发现DFN[5] = LOW[5] = 4, 于是节点5出栈，{5}为一个强连通分量;

2.返回节点4:

代码(6): LOW[4] = min(LOW[4], LOW[5]) = min(3, 4) = 3;
代码(9)-(13): 节点4的后续边已经遍历完成, 退出节点4时, DFN[4] = LOW[4] = 3; 退栈到节点4出栈，{4}为一个强连通分量;

3.返回节点2:

代码(6): LOW[2] = min(LOW[2], LOW[4]) = min(2, 3) = 2;

4.从节点2继续搜索到节点3:

代码(4)-(5): 继续遍历节点2的后续边, 找到节点3;
代码(1)-(2): 把3加入堆栈, Index = 5, DFN[3] = LOW[3] = 5;
代码(3)-(8): 发现节点3向节点0有边(3 -> 0)，且节点0在栈中，所以LOW[3] = min(LOW[3], DFN[0]) = min(5, 1) = 1。
代码(3)-(8): 发现节点3向节点5有边(3 -> 5), 但节点5已出栈;