擴展或修改強連通演算法

『壹』 請問數據結構中圖的強連通分量是什麼能具體解釋一下嗎

強連通分量是有向圖中的概念，就是每一個頂點到其它點都由路徑，注意有方向。

step1：對原圖G進行深度優先遍歷，記錄每個節點的離開時間。

step2：選擇具有最晚離開時間的頂點，對反圖GT進行遍歷，刪除能夠遍歷到的頂點，這些頂點構成一個強連通分量。

step3：如果還有頂點沒有刪除，繼續step2，否則演算法結束。

如果把求出來的每個強連通分量收縮成一個點，並且用求出每個強連通分量的順序來標記收縮後的節點，那麼這個順序其實就是強連通分量收縮成點後形成的有向無環圖的拓撲序列。

(1)擴展或修改強連通演算法擴展閱讀：

Kosaraju演算法的第二次深搜隱藏了一個拓撲性質，而Tarjan演算法和Gabow演算法省略了第二次深搜，所以，它們不具有拓撲性質。

Tarjan演算法用堆棧和標記，Gabow用兩個堆棧（其中一個堆棧的實質是代替了Tarjan演算法的標記部分）來代替Kosaraju演算法的第二次深搜，所以只用一次深搜，效率比Kosaraju演算法要高。

在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan演算法有了解的都應該清楚，那麼Tarjan演算法中的判斷根我們用什麼來代替呢？想想，其實就是看看第二個堆棧的頂元素是不是當前頂點就可以了。

『貳』 強連通分量的Kosaraju演算法思路

這個演算法可以說是最容易理解，最通用的演算法，其比較關鍵的部分是同時應用了原圖G和反圖GT。步驟1：先用對原圖G進行深搜形成森林(樹)，步驟2：然後任選一棵樹對其進行深搜(注意這次深搜節點A能往子節點B走的要求是EAB存在於反圖GT)，能遍歷到的頂點就是一個強連通分量。餘下部分和原來的森林一起組成一個新的森林，繼續步驟2直到
沒有頂點為止。
改進思路：
當然，基本思路實現起來是比較麻煩的(因為步驟2每次對一棵樹進行深搜時，可能深搜到其他樹上去，這是不允許的，強連通分量只能存在單棵樹中(由開篇第一句話可知))，我們當然不這么做，我們可以巧妙的選擇第二深搜選擇的樹的順序，使其不可能深搜到其他樹上去。想像一下，如果步驟2是從森林裡選擇樹，那麼哪個樹是不連通(對於GT來說)到其他樹上的呢？就是最後遍歷出來的樹，它的根節點在步驟1的遍歷中離開時間最晚，而且可知它也是該樹中離開時間最晚的那個節點。這給我們提供了很好的選擇，在第一次深搜遍歷時，記錄時間i離開的頂點j，即numb[i]=j。那麼，我們每次只需找到沒有找過的頂點中具有最晚離開時間的頂點直接深搜(對於GT來說)就可以了。每次深搜都得到一個強連通分量。
隱藏性質:
分析到這里，我們已經知道怎麼求強連通分量了。但是，大家有沒有注意到我們在第二次深搜選擇樹的順序有一個特點呢？如果在看上述思路的時候，你的腦子在思考，相信你已經知道了！！！它就是：如果我們把求出來的每個強連通分量收縮成一個點，並且用求出每個強連通分量的順序來標記收縮後的節點，那麼這個順序其實就是強連通分量收縮成點後形成的有向無環圖的拓撲序列。為什麼呢？首先，應該明確搜索後的圖一定是有向無環圖呢？廢話，如果還有環，那麼環上的頂點對應的所有原來圖上的頂點構成一個強連通分量，而不是構成環上那麼多點對應的獨自的強連通分量了。然後就是為什麼是拓撲序列，我們在改進分析的時候，不是先選的樹不會連通到其他樹上（對於反圖GT來說），也就是後選的樹沒有連通到先選的樹，也即先出現的強連通分量收縮的點只能指向後出現的強連通分量收縮的點。那麼拓撲序列不是理所當然的嗎？這就是Kosaraju演算法的一個隱藏性質。
Kosaraju_Algorithm:
step1：對原圖G進行深度優先遍歷，記錄每個節點的離開時間。
step2：選擇具有最晚離開時間的頂點，對反圖GT進行遍歷，刪除能夠遍歷到的頂點，這些頂點構成一個強連通分量。
step3：如果還有頂點沒有刪除，繼續step2，否則演算法結束。
C++
#include
#include
using namespace std;const int MAXN=110;int n;bool flag[MAXN];//訪問標志數組int belg[MAXN];//存儲強連通分量,其中belg[i]表示頂點i屬於第belg[i]個強連通分量int numb[MAXN];//結束時間標記,其中numb[i]表示離開時間為i的頂點AdjTableadj[MAXN],radj[MAXN];//鄰接表,逆鄰接表//用於第一次深搜,求得numb[1..n]的值voidVisitOne(intcur,int&sig){flag[cur]=true;for(inti=1;i<=adj[cur][0];++i){if(false==flag[adj[cur][i]]){VisitOne(adj[cur][i],sig);}}numb[++sig]=cur;}//用於第二次深搜,求得belg[1..n]的值voidVisitTwo(intcur,intsig){flag[cur]=true;belg[cur]=sig;for(inti=1;i<=radj[cur][0];++i){if(false==flag[radj[cur][i]]){VisitTwo(radj[cur][i],sig);}}}//Kosaraju演算法,返回為強連通分量個數intKosaraju_StronglyConnectedComponent(){inti,sig;//第一次深搜memset(flag+1,0,sizeof(bool)*n);for(sig=0,i=1;i<=n;++i){if(false==flag[i]){VisitOne(i,sig);}}//第二次深搜memset(flag+1,0,sizeof(bool)*n);for(sig=0,i=n;i>0;--i){if(false==flag[numb[i]]){VisitTwo(numb[i],++sig);}}returnsig;}

『叄』 強連通的概念

在計算機圖論中,強連通（Strongly Connected）是指有向圖G（Directed Graph）中任意兩點v1、v2之間都存在著v1到v2的路徑(path,若途徑的點和邊都不重復,則稱為路徑)及v2到v1的路徑。
定理：
一個有向圖是強連通的，當且僅當G中有一個迴路，它至少包含每個節點一次。
證明：
充分性
如果G中有一個迴路，它至少包含每個節點一次，則G中任兩個節點都是互相可達的，故G是強連通圖。
必要性
如果有向圖是強連通的，則任兩個節點都是相互可達。故必可做一迴路經過圖中所有各點。若不然則必有一迴路不包含某一結點v，並且v與迴路上的個節點就不是相互可達，與強連通條件矛盾。 Tarjan演算法是基於對圖深度優先搜索的演算法，每個強連通分量為搜索樹中的一棵子樹。搜索時，把當前搜索樹中未處理的節點加入一個堆棧，回溯時可以判斷棧頂到棧中的節點是否為一個強連通分量。
定義DFN(u)為節點u搜索的次序編號(時間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節點的次序號。由定義可以得出，
Low(u)=Min{DFN(u),Low(v),(u,v)為樹枝邊，u為v的父節點
DFN(v),(u,v)為指向棧中節點的後向邊(非橫叉邊)}
當DFN(u)=Low(u)時，以u為根的搜索子樹上所有節點是一個強連通分量。
演算法偽代碼如下
tarjan(u)
{
DFN[u]=Low[u]=++Index // 設定次序編號和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 S) // 如果節點v還在棧內
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u]) // 如果節點u是強連通分量的根
repeat
v = S.pop // 將v退棧，為該強連通分量中一個頂點
print v
until (u== v)
}
接下來是對演算法流程的演示。
從節點1開始DFS，把遍歷到的節點加入棧中。搜索到節點u=6時，DFN[6]=LOW[6]，找到了一個強連通分量。退棧到u=v為止，{6}為一個強連通分量。
返回節點5，發現DFN[5]=LOW[5]，退棧後{5}為一個強連通分量。
返回節點3，繼續搜索到節點4，把4加入堆棧。發現節點4像節點1的後向邊，節點1還在棧中，所以LOW[4]=1。節點6已經出棧，不再訪問6，返回3，(3,4)為樹枝邊，所以LOW[3]=LOW[4]=1。
繼續回到節點1，最後訪問節點2。訪問邊(2,4)，4還在棧中，所以LOW[2]=4。返回1後，發現DFN[1]=LOW[1]，把棧中節點全部取出，組成一個連通分量{1,3,4,2}。
至此，演算法結束。經過該演算法，求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。
可以發現，運行Tarjan演算法的過程中，每個頂點都被訪問了一次，且只進出了一次堆棧，每條邊也只被訪問了一次，所以該演算法的時間復雜度為O(N+M)。
求有向圖的強連通分量還有一個強有力的演算法，為Kosaraju演算法。Kosaraju是基於對有向圖及其逆圖兩次DFS的方法，其時間復雜度也是 O(N+M)。與Trajan演算法相比，Kosaraju演算法可能會稍微更直觀一些。但是Tarjan只用對原圖進行一次DFS，不用建立逆圖，更簡潔。 在實際的測試中，Tarjan演算法的運行效率也比Kosaraju演算法高30%左右。此外，該Tarjan演算法與求無向圖的雙連通分量(割點、橋)的Tarjan演算法也有著很深的聯系。學習該Tarjan演算法，也有助於深入理解求雙連通分量的Tarjan演算法，兩者可以類比、組合理解。 求有向圖的強連通分量的Tarjan演算法是以其發明者Robert Tarjan命名的。Robert Tarjan還發明了求雙連通分量的Tarjan演算法，以及求最近公共祖先的離線Tarjan演算法，在此對Tarjan表示崇高的敬意。
void tarjan(int i)
{
int j;
DFN[i]=LOW[i]=++Dindex;
instack[i]=true;
Stap[++Stop]=i;
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (!DFN[j])
{
tarjan(j);
if (LOW[j]<LOW[i])
LOW[i]=LOW[j];
}
else if (instack[j] && DFN[j]<LOW[i])
LOW[i]=DFN[j];
}
if (DFN[i]==LOW[i])
{
Bcnt++;
do
{
j=Stap[Stop--];
instack[j]=false;
Belong[j]=Bcnt;
}
while (j!=i);
}
}
void solve()
{
int i;
Stop=Bcnt=Dindex=0;
memset(DFN,0,sizeof(DFN));
for (i=1;i<=N;i++)
if (!DFN[i])
tarjan(i);
}

『肆』 怎麼用c語言和數據結構來編寫一個判斷有向圖是否為強連通圖的演算法

強連通圖表明任意兩點之間可以互相到達。
方案1：判斷結點A可以到達的點的方法如下：
首先SA = {A}；
while 1
取SA中任意沒有被去過的點x，根據以x為起點的有向線段，判斷x可以直接到達的點，然後這些點加入SA；
如此循環，直到SA中的點的個數沒有變化了
end
這樣得到的集合SA是所有A可以到達的點的一個集合。
判斷SA 是否等於S，若不等於S，表明不是強連通。

如此循環，求出所有S中的點的能夠到達的點集。如果所有的點集都等於S表明強連通圖。

方案2：可以優化1

『伍』 如何實現強連通圖的優化

暑假 王建德和朱全民跟我們說了,不記得了

『陸』 什麼叫：強連通 單向連通 弱連通 不連通

下面是這強連通、單向連通、弱連通、不連通的定義：

連通分量：無向圖 G的一個極大連通子圖稱為 G的一個連通分量（或連通分支）。連通圖只有一個連通分量，即其自身；非連通的無向圖有多個連通分量。

強連通圖：有向圖 G=(V,E) 中，若對於V中任意兩個不同的頂點 x和 y，都存在從x到 y以及從 y到 x的路徑，則稱 G是強連通圖。相應地有強連通分量的概念。強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連分量。

單向連通圖：設G=<V,E>是有向圖，如果u->v意味著圖G至多包含一條從u到v的簡單路徑，則圖G為單連通圖。

弱連通圖：將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則有向圖是弱連通圖。

初級通路：通路中所有的頂點互不相同。初級通路必為簡單通路，但反之不真。

在圖論中，連通圖基於連通的概念。在一個無向圖 G 中，若從頂點i到頂點j有路徑相連（當然從j到i也一定有路徑），則稱i和j是連通的。如果 G 是有向圖，那麼連接i和j的路徑中所有的邊都必須同向。

如果圖中任意兩點都是連通的，那麼圖被稱作連通圖。如果此圖是有向圖，則稱為強連通圖（注意：需要雙向都有路徑）。圖的連通性是圖的基本性質。

(6)擴展或修改強連通演算法擴展閱讀：

強連通圖的邊問題：

有n個頂點的強連通圖最多有n（n-1）條邊，最少有n條邊。

1、最多的情況：即n個頂點中兩兩相連，若不計方向，n個點兩兩相連有n（n-1）/2條邊，而由於強連通圖是有向圖，故每條邊有兩個方向，n（n-1）/2×2=n（n-1），故有n個頂點的強連通圖最多有n（n-1）條邊。

2、最少的情況：即n個頂點圍成一個圈，且圈上各邊方向一致，即均為順時針或者逆時針，此時有n條邊。

求無向圖的連通分量：

作為遍歷圖的應用舉例，下面我們來討論如何求圖的連通分量。無向圖中的極大連通子圖稱為連通分量。求圖的連通分量的目的，是為了確定從圖中的一個頂點是否能到達圖中的另一個頂點，也就是說，圖中任意兩個頂點之間是否有路徑可達。

對於連通圖，從圖中任一頂點出發遍歷圖，可以訪問到圖的所有頂點，即連通圖中任意兩頂點間都是有路徑可達的。

參考資料來源：網路-連通圖

『柒』 強連通分量的Gabow演算法思路

這個演算法其實就是Tarjan演算法的變異體，我們觀察一下，只是它用第二個堆棧來輔助求出強連通分量的根，而不是Tarjan演算法裡面的indx[]和mlik[]數組。那麼，我們說一下如何使用第二個堆棧來輔助求出強連通分量的根。
我們使用類比方法，在Tarjan演算法中，每次mlik[i]的修改都是由於環的出現(不然，mlik[i]的值不可能變小)，每次出現環，在這個環裡面只剩下一個mlik[i]沒有被改變(深度最低的那個)，或者全部被改變，因為那個深度最低的節點在另一個環內。那麼Gabow演算法中的第二堆棧變化就是刪除構成環的節點，只剩深度最低的節點，或者全部刪除，這個過程是通過出棧來實現，因為深度最低的那個頂點一定比前面的先訪問，那麼只要出棧一直到棧頂那個頂點的訪問時間不大於深度最低的那個頂點。其中每個被彈出的節點屬於同一個強連通分量。那有人會問：為什麼彈出的都是同一個強連通分量？因為在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan演算法有了解的都應該清楚，那麼Tarjan演算法中的判斷根我們用什麼來代替呢？想想，其實就是看看第二個堆棧的頂元素是不是當前頂點就可以了。
現 在，你應該明白其實Tarjan演算法和Gabow演算法其實是同一個思想的不同實現，但是，Gabow演算法更精妙，時間更少(不用頻繁更新mlik[])。 Gabow_Algorithm:
步驟1:
找一個沒有被訪問過的節點v，goto step2(v)。否則，演算法結束。
步驟2(v):
將v壓入堆棧stk1[]和stk2[]
對於v所有的鄰接頂點u：
1) 如果沒有訪問過，則step2(u)
2) 如果訪問過，但沒有刪除，維護stk2[](處理環的過程)
如果stk2[]的頂元素==v，那麼輸出相應的強連通分量 C++：#include<iostream>usingnamespacestd;constintMAXN=110;typedefintAdjTable[MAXN];//鄰接表類型intn;intintm[MAXN];//標記進入頂點時間intbelg[MAXN];//存儲強連通分量,其中belg[i]表示頂點i屬於第belg[i]個強連通分量intstk1[MAXN];//輔助堆棧intstk2[MAXN];//輔助堆棧AdjTableadj[MAXN];//鄰接表//深搜過程,該演算法的主體都在這里voidVisit(intcur,int&sig,int&scc_num){inti;intm[cur]=++sig;stk1[++stk1[0]]=cur;stk2[++stk2[0]]=cur;for(i=1;i<=adj[cur][0];++i){if(0==intm[adj[cur][i]]){Visit(adj[cur][i],sig,scc_num);}elseif(0==belg[adj[cur][i]]){while(intm[stk2[stk2[0]]]>intm[adj[cur][i]]){--stk2[0];}}}if(stk2[stk2[0]]==cur){--stk2[0];++scc_num;do{belg[stk1[stk1[0]]]=scc_num;}while(stk1[stk1[0]--]!=cur);}}//Gabow演算法,求解belg[1..n],且返回強連通分量個數,intGabow_StronglyConnectedComponent(){inti,sig,scc_num;memset(belg+1,0,sizeof(int)*n);memset(intm+1,0,sizeof(int)*n);sig=0;scc_num=0;stk1[0]=0;stk2[0]=0;for(i=1;i<=n;++i){if(0==intm[i]){Visit(i,sig,scc_num);}}returnscc_num;}Pascalproceretarjan(r:longint);varx,i,j:longint;begininc(timez);time[r]:=timez;low[r]:=timez;inc(top);zh[top]:=r;fori:=p1[r]top2[r]dobeginj:=e[i].y;iftime[j]=0thentarjan(j);iflow[j]<low[r]thenlow[r]:=low[j];end;iftime[r]=low[r]thenrepeatx:=zh[top];num[x]:=r;low[x]:=n+1;//這句話千萬別忘了dec(top);untilx=r;end;

『捌』 用C語言和數據結構（只能用這兩種）來編寫一個判斷有向圖是否為強連通圖的演算法

這是一個遞歸演算法：
1、一個節點的圖是強連通的，這是遞歸終止條件
2、G(n)的強連通性變為：圖G（n-1）和節點g（n）和G(n-1)的聯通問題。
採用遞歸方式，具體演算法要結合你的存儲結構實現