資源描述：
《有向圖的強連通分量》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、強連通分量一個有向圖中，如果節(jié)點i能夠通過一些邊到達節(jié)點j，就簡寫成i能到達j。如果對于任意兩個節(jié)點i,j均有i能到達j或j能到達i，則說此圖是連通的。如果對于任意兩個節(jié)點i,j均有i能到達j且j能到達i，則說此圖是強連通的。對于一個無向圖，說強聯(lián)通沒有意義，因為此時強連通就是連通。而對于一個有向圖，它不一定是強連通的，但可以分為幾個極大的強連通子圖（“極大”的意思是再加入任何一個頂點就不滿足強連通了）。這些子圖叫做這個有向圖的強連通分量。在上圖中，強連通分量是A{1},B{2,4},C{3,5,6,7}。在一個強連通分量中的節(jié)點由于有著
2、相似的拓撲性質(zhì)，所以我們可以將其緊縮為一個節(jié)點（這讓我想到了什么？化學(xué)里的“族”），于是就大大減小了圖的規(guī)模。比如上圖緊縮為A,B,C三個節(jié)點后，整個圖就成為了B←A→C的簡單形式。所以強連通分量是一個很有意義的東西。然而如果根據(jù)定義，對每個節(jié)點進行一次O(n2)的DFS以求出它所能到達的頂點的話，整個算法的時間復(fù)雜度就是遲鈍的O(n3)。下面將介紹兩種用O(n2)求強連通分量的算法：Kosaraju算法和Tarjan算法。Kosaraju算法Kosaraju算法基于以下思想：強連通分量一定是某種DFS形成的DFS樹森林。Kosaraju
3、算法給出了更具體的方式：①任意進行一次DFS，記錄下每個節(jié)點的結(jié)束時間戳f[i]。②按f[i]的大小對節(jié)點進行排序（從小到大）。③以②的排序結(jié)果為順序再進行一次DFS，所得的DFS樹森林即為強連通分量。這次DFS可以用Floodfill進行，把每個強連通分量標(biāo)上不同序號。（這就是OI界傳說中的“求強連兩遍DFS的算法”）比如上圖，我們可以得到：d[1]=1f[1]=14d[2]=2f[2]=5d[3]=6f[3]=13d[4]=3f[4]=4d[5]=7f[5]=8d[6]=9f[6]=12d[7]=10f[7]=11根據(jù)f[i]排序得：
4、④②⑤⑦⑥③①（發(fā)現(xiàn)了什么？就是后序遍歷），再按照這個順序進行DFS即可。程序：vara:array[1..1000,1..1000]oflongint;b,flag:array[1..1000]oflongint;n,i,j,m,k:longint;proceduredfs(x:longint);varj:longint;beginflag[x]:=1;forj:=1tondoif(flag[j]=0)and(a[x,j]>0)thendfs(j);inc(m);b[m]:=x;end;procedurefill(x,k:longint
5、);varj:longint;beginflag[x]:=k;forj:=ndownto1doif(flag[b[j]]=0)and(a[b[j],x]>0)thenfill(b[j],k);end;beginreadln(n);fori:=1tondobeginforj:=1tondoread(a[i,j]);readln;end;m:=0;fillchar(flag,sizeof(flag),0);fori:=1tondoifflag[i]=0thendfs(i);fillchar(flag,sizeof(flag),0);k:=0;
6、fori:=ndownto1doifflag[b[i]]=0thenbegininc(k);fill(b[i],k);end;fori:=1tokdobeginforj:=1tondoifflag[j]=ithenwrite(j,'');writeln;end;end.Tarjan算法Tarjan算法只要一遍DFS，效率高于Kosaraju。它在技術(shù)上有了很大改進。它基于的思想是：強連通分量是DFS樹中的子樹（無論你如何進行DFS）。Tarjan算法的過程是：①在DFS樹中，設(shè)low[x]是x或x的后代能夠達到的最高的祖先。初始化時low
7、[x]設(shè)為x。②進行DFS，在結(jié)束節(jié)點x時計算low[x]。計算的方法是：找出x能夠到達的所有節(jié)點i，應(yīng)保證low[i]是x的祖先，即low[i]是灰點。low[x]=highest(low[i])，即d[low[i]]最小。③若low[x]=x，則以x為根的子樹就是一個強連通分量，輸出并將其從樹中刪去。比如上圖（又是上圖。。沒辦法，圖片空間有限制），我們依次得出：low[4]=low[2]=2low[2]=low[4]=2//{4,2}為強連通分量low[5]=low[3]=3low[7]=low[5]=3low[6]=low[7]=3
8、low[3]=low[6]=3//{5,7,6,3}為強連通分量low[1]=1//{1}為強連通分量感謝ChenGang同學(xué)的提醒，我原來的程序中的輸出有些問題?，F(xiàn)在采用堆棧的方法，dfs到
