Tarjan算法——求有向图强连通分支

Posted on 2011-07-28 20:57 Mato_No1 阅读(1458) 评论(0)  编辑 收藏 引用 所属分类: 图算法
在图DFS的过程中,给每个点设立两个附加值dfn和low。dfn[i]表示点i被发现(变灰)的时间,也就是“发现次序”。而low[i]表示i能够到达的dfn值最小的i的祖先结点或i本身的dfn值,即low[i]=min{dfn[i], dfn[j], low[k]}(其中j为满足以下条件的点:图中存在边<i, j>且这条边在遍历到的时候j在栈中(这个栈的具体说明见下);k为遍历树中i的某个子结点,)。

Tarjan算法就是在图DFS过程中,得到每个点的dfn值和low值,并且设立一个栈,点变灰的时候入栈,在某个点i的low值真正确定后(容易发现,一个点只有变黑了,它的low值才真正确定),若low[i]=dfn[i],则将栈中点i及其上面的所有点全部弹出(这些点一定是以i为根的子树中的结点,因为它们比i后入栈,却比i先出栈),这些点组成一个强连通分支,这样在图DFS遍历完后,即可得到所有的强连通分支。

下面证明结点i变黑时,若low[i]=dfn[i],则
i及其所有未出栈的后代组成一个强连通分支。
证明这个需要分两步:
【1】i的所有未出栈的后代与i处于同一个强连通分支。
设j是i的某个后代且j在i变黑时尚未出栈。显然i可达j,因此只需证明j可达i。
在遍历树中,从i到j路径上除i外的所有结点的low值都小于dfn值(否则,设这条路径上存在结点k,k≠i,low[k]=dfn[k]。因为k比i先变黑,所以在k变黑时,其所有后代就会出栈,这与j在i变黑时仍未出栈矛盾,故这样的结点k不存在)。设dfn[x]=low[j],则根据low的定义以及low[j]<dfn[j]得,必然是j的祖先且从j先往下再经过一条逆向边可以到达点x,并且,x不可能是i的祖先(若x是i的祖先,则i先往下再经过一条逆向边可达x,因此dfn[x]>=low[i],又因为dfn[x]<dfn[i],所以low[i]<dfn[i],这与low[i]=dfn[i]矛盾),也就是x位于路径i->j上且x≠j。若x=i,则j可达i,结束,否则先从j到达x,再将x当成j,继续往上……这样最终必然能到达点i。因此j可达i,即j与i处于同一个强连通分支。
【2】不是i的未出栈的后代不与i处于同一个强连通分支。
设j不是i的未出栈的后代,则j有两种情况:
(1)j是i的后代,且在i变黑前已经出栈:
此时,i->j路径上必然存在一个点k,满足k≠i,且dfn[k]=low[k](这样的k可能有多个,此时取最深的那个为k),当k变黑时j出栈。这时,由与【1】类似的推导过程可得,j不断往上到达的最上层祖先结点也只能是k,到不了i,故j不可达i,也即j与i不处于同一个强连通分支;
(2)j不是i的后代,考虑当i变黑时,j的颜色:
<1>白色:此时,若i可达j,则j在i变黑前,就会成为i的后代,这与j不是i的后代矛盾,故i一定不可达j,也即j与i不处于同一个强连通分支;
<2>灰色:若j为灰色,则j一定是i的祖先,若i可达j,根据low的定义可得,必有low[i]<=dfn[j]<dfn[i],这与low[i]=dfn[i]矛盾,故i不可达j,也即j与i不处于同一个强连通分支;
<3>黑色:若j不是i的后代,且比i先变黑,则必然是在i变灰前j已经变黑。这时,若j可达i,则i会成为j的后代,也即j是i的祖先,这样在i变黑时,j应为灰色,矛盾,故j不可达i,也即j与i不处于同一个强连通分支;
综上可得,i、j一定不处于同一个强连通分支。故原命题得证,也就证明了Tarjan算法是可以求出有向图的所有强连通分支的。

时间复杂度分析:由于每个点都要入栈一次,出栈一次,每条边都要被访问一次,所以总时间复杂度为O(N+M)。

写代码时注意事项:
(1)要用人工栈实现DFS,不可用递归,防止爆栈;另外注意不要将这个人工栈与上面说到的“栈”弄混,本沙茶下面的代码中,用于搜索、回溯的人工栈为stk0,而用于找强分支的栈为stk;
(2)注意边界情况;
(3)注意在出栈时要将V值设为2;

(4)注意计算low[i]时,需要考虑非i的祖先,但仍在栈中的结点,它们也被视为i的“祖先”。

核心代码:
void solve()
{
    re(i, n) {V[i] 
= vst[i] = 0; st[i] = E[i].next;}
    
int x, y, x0, tp, tp0, ord = 0, No = 0;
    
bool fd;
    re(i, n) 
if (!V[i]) {
        stk[tp 
= 0= stk0[tp0 = 0= i; vst[i] = 1; low[i] = dfn[i] = ++ord; V[i] = 1;
        
while (tp0 >= 0) {
            x 
= stk0[tp0]; fd = 0;
            
for (int p=st[x]; p != x; p=E[p].next) {
                y 
= E[p].b;
                
if (!V[y]) {
                    fd 
= 1; stk[++tp] = stk0[++tp0] = y; vst[y] = 1; low[y] = dfn[y] = ++ord; V[y] = 1; st[x] = E[p].next; break;
                } 
else if (vst[y] && dfn[y] < low[x]) low[x] = dfn[y];
            }
            
if (!fd) {
                V[x] 
= 2;
                
if (low[x] == dfn[x]) {while (stk[tp] != x) {vst[stk[tp]] = 0; w[stk[tp--]] = No;} vst[x] = 0; w[stk[tp--]] = No++;}
                
if (tp0) {x0 = stk0[tp0 - 1]; if (low[x] < low[x0]) low[x0] = low[x];} tp0--;
            }
        }
    }
    re(i, n) {reslen[i] 
= 0for (int p=E[i].next; p != i; p=E[p].next) if (w[i] == w[E[p].b]) reslen[i]++;}
}



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理