tarjan算法、Kosaraju算法——求有向图强连通分量

Tarjan算法

Tarjan算法是一种基于DFS的算法，使用栈来存储访问过程中的顶点

先引入两个非常重要的数组：dfn 与 low

dfn：顶点被搜索到的“时间戳”，用于记录顶点被搜到的次序，一个顶点的时间戳记录后就不再改变

low：在本次DFS搜索中（最外层循环），且仍在栈中的最小时间戳，像是确立了一个关系，low相等的点在同一强连通分量中。

注意初始化时 dfn= low = ++cnt

算法思路：

图不一定是强连通图，所以跑Tarjan时要枚举每个点，若dfn == 0，进行深搜。

对于搜到的顶点，寻找以其为弧尾的顶点，判断这些顶点是否已经被搜索过，若没有（显然也一定没有入栈），则进行搜索；若该点已经入栈，说明形成了环，则更新low

在DFS回溯时不断比较low，不断取最小的low值。如果dfn[x]==low[x] 则说明找到了一个强连通分量，并可以以x为起点。对栈进行弹出操作，直到x被弹出，这些被弹出的顶点构成一个强连通分量的顶点集

递归函数代码:

void tarjan(int now)
{
    dfn[now]=low[now]=++cnt;  //初始化
    stack[++t]=now;　　　　　　 //入栈操作
    v[now]=1;　　　　　　　　    //v[]代表该点是否已入栈
    for(int i=f[now];i!=-1;i=e[i].next)  //邻接表存图
        if(!dfn[e[i].v]) 　　　　　　　　　 //判断该点是否被搜索过
        {
            tarjan(e[i].v);
            low[now]=min(low[now],low[e[i].v]); //回溯时更新low[ ]，取最小值
        }
        else if(v[e[i].v])
            low[now]=min(low[now],dfn[e[i].v]); //一旦遇到已入栈的点，就将该点作为连通量的根
　　　　　　　　　　　　　　　　　　　　　　　  //这里用dfn[e[i].v]更新的原因是：这个点可能
　　　　　　　　　　　　　　　　　　　　　　　　//已经在另一个强连通分量中了但暂时尚未出栈，所
　　　　　　　　　　　　　　　　　　　　　　　　//以now不一定能到达low[e[i].v]但一定能到达
　　　　　　　　　　　　　　　　　　　　　　　　//dfn[e[i].v].
    if(dfn[now]==low[now])
    {
        int cur;
        do
        {
            cur=stack[t--];
            v[cur]=false;                       //不要忘记出栈
        }while(now!=cur);
    }
}

Kosaraju算法

Kosaraju给出的方案：对原图取反，然后从反向图的任意节点开始进行DFS的逆后序遍历。根据逆后序遍历得到的序列进行DFS遍历（与无向图找连通分量类似）一定可以找到各强连通分量。

DFS的逆后序遍历是指：如果当前顶点未访问，先遍历完与当前顶点相连的且未被访问的所有其它顶点，然后将当前顶点加入栈中，最后栈中从栈顶到栈底的顺序就是我们需要的顶点顺序。

也就是说，使用Kosaraju算法求强连通分量分为两步

• 对原图取反，从任意一个顶点开始对反向图进行逆后续DFS遍历
• 按照逆后续遍历中栈中的顶点出栈顺序，对原图进行DFS遍历，一次DFS遍历中访问的所有顶点都属于同一强连通分量

参考文章链接