圖的連通性問題

圖的連通性問題第一頁，共十六頁，2022年，8月28日￡7.4圖的連通性問題￡7.4.1無向圖的連通分量和生成樹廣度優(yōu)先生成樹：在連通圖中，由廣度優(yōu)先搜索得到的生成樹。（1）連通圖在對(duì)無向圖進(jìn)行遍歷時(shí)，對(duì)于連通圖，僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有結(jié)點(diǎn)。深度優(yōu)先生成樹：在連通圖中，由深度優(yōu)先搜索得到的生成樹。（2）非連通圖在對(duì)無向圖進(jìn)行遍歷時(shí)，對(duì)于非連通圖，需從多個(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)先搜索得到的生成森林。第二頁，共十六頁，2022年，8月28日?qǐng)D7.11生成樹和生成森林A1L2F6C7M3J4B5D8E9G10K11I13H12

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

G3ABCDE

FGH

IKLM

J第三頁，共十六頁，2022年，8月28日(連通網(wǎng)的)最小生成樹

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問題：第四頁，共十六頁，2022年，8月28日構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價(jià)于：算法一：（普里姆算法）第五頁，共十六頁，2022年，8月28日

取圖中任意一個(gè)頂點(diǎn)v作為生成樹的根，之后往生成樹上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有n-1個(gè)頂點(diǎn)為止。普里姆算法的基本思想:第六頁，共十六頁，2022年，8月28日abcdegf195141827168213127例如:aedcbgf148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67第七頁，共十六頁，2022年，8月28日在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U

和尚未落在生成樹上的頂點(diǎn)集V-U

，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:UV-U第八頁，共十六頁，2022年，8月28日設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前V－U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：struct{VertexTypeadjvex;//U集中的頂點(diǎn)序號(hào)

VRTypelowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];第九頁，共十六頁，2022年，8月28日abcdegf195141827168213127aedcbaaa19141814例如:e12ee8168d3dd7213c55

19mm14m18195712mmm53mmmm73821m1412m8m16mmm21m2718mmm1627第十頁，共十六頁，2022年，8月28日voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹

k=LocateVex(G,u);

for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)

closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;//初始，U＝{u}

for(i=0;i<G.vexnum;++i){}繼續(xù)向生成樹上添加頂點(diǎn);第十一頁，共十六頁，2022年，8月28日

k=minimum(closedge);

//求出加入生成樹的下一個(gè)頂點(diǎn)(k)

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹上一條邊

closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集

for(j=0;j<G.vexnum;++j)//修改其它頂點(diǎn)的最小邊

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};

第十二頁，共十六頁，2022年，8月28日具體做法:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。考慮問題的出發(fā)點(diǎn):為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄旱谑?，共十六頁，2022年，8月28日abcdegf195141827168213127aedcbgf148531621例如:7121819第十四頁，共十六頁，2022年，8月28日算法描述:構(gòu)造非連通圖ST=(V,{});k=i=0;//k計(jì)選中的邊數(shù)

while(k<n-1){++i;

檢查邊集E中第i條權(quán)值最小的邊(u,v);