連通分量演算法
① 設計一個演算法,求無向圖G(採用鄰接表存儲)的連通分量的個數
int Count(Graph G)
{
int count=0;
for(v=0;v<G.vexnum;++v) visited[v]=false; //初始化每個節點的被訪問標記
for(v=0;v<G.vexnum;++v)
{
if(!visited[v])
{
DFS(G,v);
count++;
}
}
return count;
}
void DFS(Graph G, int)
{
visited[v]=true;
for(w=FirstAdjVex(G,v); w; w=NextAgjVex(G,v,w))
{
if(!visited[w]) DFS(G,w)
}
}
② 請問如何求(有向/無向)圖的強連通分量，還有，基礎一點，怎麼求有幾個連通圖啊
求強連通分量的演算法有tarjan和kosaraju 兩種演算法
相較之下 tarjan寫起來比較簡單 Kosaraju比較麻煩
但是想起來 Kosaraju比較簡單
其他求強連通分量的演算法 要是還有的話 估計就是需要更高深的數據結構的演算法了
建議還是學下tarjan 因為他可以幫你做很多事 比如 求橋 求割點 縮環 而且寫起來也很簡單
連通圖的求法可以直接DFS 每次DFS到一個點 就把它記錄成已到達 然後繼續向下搜索 每次DFS就可以求出一個連通圖
附上tarjan的代碼
var
next,head,point:array[1..1000] of longint;
time,tot,i,j,n,m,x,y,t:longint;
v:array[1..10000] of byte;
f,z,q:array[1..1000] of longint;
low,rea:array[1..10000] of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
procere add(x,y:longint);
begin
inc(tot);
next[tot]:=head[x];
head[x]:=tot;
point[tot]:=y;
end;
procere dfs(x:Longint);
var
i,j:longint;
begin
inc(time);
low[x]:=time;
rea[x]:=time;
v[x]:=1;
inc(t);
z[t]:=x;
j:=head[x];
while j<>0 do
begin
if v[point[j]]=0 then dfs(point[j]);
if v[point[j]]<2 then low[x]:=min(low[point[j]],low[x]);
j:=next[j];
end;
if low[x]=rea[x] then
begin
inc(tot);
while z[t+1]<>x do
begin
inc(q[tot]);
f[z[t]]:=tot;
v[z[t]]:=2;
dec(t);
end;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
add(x,y);
end;
tot:=0; time:=0;
for i:=1 to n do
if v[i]=0 then dfs(i);
//writeln(tot);
for i:=1 to n do
if q[f[i]]<>1 then writeln('T') else writeln('F');
end.
③ 廣度優先演算法和深度優先演算法哪個可以求無向圖的所有連通分量，具體什麼原理
你好，廣度優先和深度優先都可以求出無向圖的所有連通分量，他們的原理都是遍歷，一個是先按廣度進行遍歷，另外一個是先按深度進行遍歷。
④ 強連通分量的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;}
⑤ 強連通分量(Kosaraju演算法)
{ //判斷各個強連通分量是否為出度為0的分量 for(int t = 0; t
⑥ 想問一下圖上的第5題 Python代碼
在這篇文章中將為大家介紹一些重要的圖演算法,以及Python 的代碼實現。 1、連通分量 具有三個連通分量的圖 將上圖中的連通分量演算法近似看作一種硬聚類演算法,該演算法旨在尋找相關數據的簇類。舉一個具體的例子:假設擁有連接世界上任意城市的.
⑦ 採用鄰接表存儲結構，編寫一個求無向圖的連通分量個數的演算法。
思路是這樣的：
1、從圖中任選一個節點，以此節點進行深度優先搜索並將訪問的節點做好標記，連通分量數加一。
2、在從圖中沒有訪問的節點集中選一個節點重復1的過程直到所有節點都被標記
⑧ 請設計一個演算法，求出無向圖G的連通分量個數
intConnect(AdjGraph*G){//參數為鄰接表int i,count=0;
DFC(G,0);//圖的深度遍歷，以0頂點開始
for(int i = 0;i<G->n;i++){
if(visited[i] == 0){//圖遍歷演算法的輔助數組，若為0則沒遍歷到，說明非連通
count++;
DFS(G,i);
}
}
if(count == 0 )//若上面循環遍歷完畢count=0則說明改圖連通，只有一個連通分量
count = 1;
return count;
}
⑨ 強連通分量的Tarjan演算法思路
這個演算法思路不難理解，由開篇第一句話可知，任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那麼其實，我們只要確定每個強連通分量的子樹的根，然後根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。那麼剩下的問題就只剩下如何確定強連通分量的根和如何從最低層開始拿出強連通分量了。
那麼如何確定強連通分量的根，在這里我們維護兩個數組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與頂點i鄰接的頂點未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發現mlik[i]==indx[i]那麼，當前頂點就是一個強連通分量的根，為什麼呢？因為如果它不是強連通分量的根，那麼它一定是屬於另一個強連通分量，而且它的根是當前頂點的祖宗，那麼存在包含當前頂點的到其祖宗的迴路，可知mlik[i]一定被更改為一個比indx[i]更小的值。
至於如何拿出強連通分量，這個其實很簡單，如果當前節點為一個強連通分量的根，那麼它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍歷的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。現 在知道如何拿出了強連通分量了吧？是的，因為當前節點是這個強連通分量中最先被壓入堆棧的，那麼在當前節點以後壓入堆棧的並且仍在堆棧中的節點都屬於這個強連通分量。當然有人會問真的嗎？假設一個節點在當前節點壓入堆棧以後壓入並且還存在，同時它不屬於該強連通分量，那麼它一定屬於另一個強連通分量，但當前節點是它的根的祖宗，那麼這個強連通分量應該在此之前已經被拿出。現 在沒有疑問了吧，那麼演算法介紹就完了。
⑩ 請問數據結構中圖的強連通分量是什麼能具體解釋一下嗎
有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。
在有向圖G中，如果兩個頂點vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。
(10)連通分量演算法擴展閱讀：
強連通分量Tarjan演算法
任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那麼只要確定每個強連通分量的子樹的根，然後根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。
維護兩個數組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與頂點i鄰接的頂點未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發現mlik[i]==indx[i]那麼，當前頂點就是一個強連通分量的根。
因為如果它不是強連通分量的根，那麼它一定是屬於另一個強連通分量，而且它的根是當前頂點的祖宗，那麼存在包含當前頂點的到其祖宗的迴路，可知mlik[i]一定被更改為一個比indx[i]更小的值。
至於拿出強連通分量，如果當前節點為一個強連通分量的根，那麼它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍歷的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。
這樣，由於當前節點是這個強連通分量中最先被壓入堆棧的，那麼在當前節點以後壓入堆棧的並且仍在堆棧中的節點都屬於這個強連通分量。
可以用反證法證明這個做法的正確性。假設一個節點在當前節點壓入堆棧以後壓入並且還存在，同時它不屬於該強連通分量，那麼它一定屬於另一個強連通分量，但當前節點是它的根的祖宗，那麼這個強連通分量應該在此之前已經被拿出。