圖的連通性問題

圖的連通性問題1￡7.4圖的連通性問題￡7.4.1無向圖的連通分量和生成樹廣度優(yōu)先生成樹：在連通圖中，由廣度優(yōu)先搜索得到的生成樹。（1）連通圖在對無向圖進(jìn)行遍歷時(shí)，對于連通圖，僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有結(jié)點(diǎn)。深度優(yōu)先生成樹：在連通圖中，由深度優(yōu)先搜索得到的生成樹。（2）非連通圖在對無向圖進(jìn)行遍歷時(shí)，對于非連通圖，需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其各個(gè)連通分量中的頂點(diǎn)集。生成森林：在非連通圖中，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過的邊一起構(gòu)成若干棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。

深度優(yōu)先生成森林：在非連通圖中，由深度優(yōu)先搜索得到的生成森林。

廣度優(yōu)先生成森林：在非連通圖中，由廣度優(yōu)先搜索得到的生成森林。2圖7.11生成樹和生成森林A1L2F6C7M3J4B5D8E9G10K11I13H12

(c) 圖7.3(a)G3的深度優(yōu)先生成森林(a)無向圖G3

G3ABCDEFGHIKLMJ3(連通網(wǎng)的)最小生成樹

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？該問題等價(jià)于：構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法一：（普里姆算法）算法二：（克魯斯卡爾算法）4構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價(jià)于：算法一：（普里姆算法）5有向圖的連通性設(shè)D=<V,E>為有向圖，對于任意的u,vV，如果存在從u到v的通路，則稱u可達(dá)v，記為uv，并規(guī)定任何頂點(diǎn)到自身總是可達(dá)的。若D中任意兩結(jié)點(diǎn)相互可達(dá)，則稱D是強(qiáng)連通的。6SCC的概念有向圖中,u可達(dá)v不一定意味著v可達(dá)u.相互可達(dá)則屬于同一個(gè)強(qiáng)連通分量(StronglyConnectedComponent,SCC)有向圖和它的轉(zhuǎn)置的強(qiáng)連通分量相同所有SCC構(gòu)成一個(gè)DAG7求強(qiáng)連通分量使用Kosaraju算法一、Kosaraju算法步驟：Step1、對有向圖G做dfs（深度優(yōu)先遍歷），記錄每個(gè)結(jié)點(diǎn)結(jié)束訪問的時(shí)間(即節(jié)點(diǎn)出棧順序，后出棧的點(diǎn)第二次先掃描)Step2、將圖G逆置，即將G中所有弧反向。Step3、按Step1中記錄的結(jié)點(diǎn)結(jié)束訪問時(shí)間從大到小對逆置后的圖做dfsStep4、得到的遍歷森林中每棵樹對應(yīng)一個(gè)強(qiáng)連通分量。8二、Kosaraju算法求解過程實(shí)例 下面結(jié)合實(shí)例說明Kosaraju算法的基本策略。圖1給出了一個(gè)有向圖G。

ACBDEFGH圖1有向圖G9 Step1：假設(shè)從DFS在遍歷時(shí)按照字母順序進(jìn)行，根據(jù)Kosaraju算法，在步驟1中我們得到的遍歷順序可以表達(dá)為 [A,[C,[B,[D,D],B],C],A][E,[F,[G,[H,H],G],F],E]越后出棧的點(diǎn)先訪問第一步所得到的順序即為：EFGHACBD Step2：根據(jù)算法第2步，將圖G逆置，得到對應(yīng)的反向圖G’如圖2所示。AC圖2逆置圖G’GHBDEFACBDEFGH圖1有向圖G10Step3：根據(jù)步驟1得到的遍歷序列，按照結(jié)點(diǎn)結(jié)束訪問時(shí)間遞減排序后的結(jié)果 EFGHACBD下面，按照該結(jié)點(diǎn)序列順序?qū)δ嬷脠DG’所深度優(yōu)先遍歷，得到的深度優(yōu)先遍歷森林如圖3所示。森林中共有4棵樹，其中(a)和(d)只有一個(gè)結(jié)點(diǎn)，這里認(rèn)為單結(jié)點(diǎn)也是一個(gè)強(qiáng)聯(lián)通分量（在實(shí)際應(yīng)用中可以根據(jù)實(shí)際需要將這種情況過濾掉）。AC圖2逆置圖G’GHBDEF圖3逆置圖G’的DFS生成森林GEFHBACD

(a)

(b)

(c)

(d)11kasaraju算法代碼#include<stdio.h>#definemax100#defineinf10000intvis[max]={0}/*是否遍歷*/,order[max]/*第二次遍歷的順序*/,id[max];/*個(gè)點(diǎn)所屬的強(qiáng)連通分量*/intn,m,number/*點(diǎn)數(shù)變數(shù)計(jì)數(shù)器*/;intmap[max][max]/*圖*/;intnet=0;voidinit()//初始化{ inti,j; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=inf; for(i=1;i<=n;i++) map[i][i]=0;}voidread()/*讀取數(shù)據(jù)*/{ inti,a,b; number=n; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); map[a][b]=1; }}12voiddfs1(intv)/*第一次遍歷確定點(diǎn)的順序*/{ inti; vis[v]=1; for(i=1;i<=n;i++) if(map[v][i]<inf&&vis[i]!=1) dfs1(i); order[number]=v;/*出棧的時(shí)候記錄順序于ORDER數(shù)組*/ number--;}voiddfs2(intv){ inti; vis[v]=1; id[v]=number;//V點(diǎn)所屬的連通分量 for(i=1;i<=n;i++) if(map[i][v]<inf&&vis[i]!=1) dfs2(i);}voidkosaraju(){ inti,j; for(i=1;i<=n;i++)//第一次DFS確定第二次DFS順序 if(!vis[i]) dfs1(i); number=0; for(i=1;i<=n;i++) vis[i]=0; for(i=1;i<=n;i++) if(vis[order[i]]!=1) { number++;//連通分量標(biāo)記 dfs2(order[i]); }}13intmain(){ inti,j; init(); read(); kosaraju(); for(i=1;i<=number;i++) { printf("第%d個(gè)強(qiáng)連通分量->",i); for(j=1;j<=n;j++) if(id[j]==i) printf("%d",j); printf("\n"); } return0;}/*8111321322434545658677886*/ACBDEFGH圖1有向圖G14POJ2186題目大意是：在一個(gè)牧群中，有N個(gè)奶牛，給定M對關(guān)系（A,B）表示A仰慕B，而且仰慕關(guān)系有傳遞性，問被所有奶牛（除了自己）仰慕的奶牛個(gè)數(shù)SampleInput第一行分別是牛的個(gè)數(shù)和仰慕關(guān)系總數(shù)33122123SampleOutput輸出被所有奶牛仰慕的編號115題目分析：因?yàn)檠瞿疥P(guān)系具有傳遞性，因此在一個(gè)強(qiáng)連通分量中，