1EssentialofLectureFifteen

：

一、圖的遍歷（深度、廣度）二、最小生成樹(shù)三、普里姆算法四、克魯斯卡爾算法第十五講圖的遍歷難點(diǎn)2

圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問(wèn)圖中所有頂點(diǎn)，并且每個(gè)頂點(diǎn)僅訪問(wèn)一次。 在圖中，訪問(wèn)部分頂點(diǎn)后，可能又沿著其他邊回到已被訪問(wèn)過(guò)的頂點(diǎn)。 為保證每一個(gè)頂點(diǎn)只被訪問(wèn)一次，必須對(duì)頂點(diǎn)進(jìn)行標(biāo)記，一般用一個(gè)標(biāo)識(shí)域tag作為對(duì)頂點(diǎn)的標(biāo)記，當(dāng)頂點(diǎn)vi未被訪問(wèn)，tag初始值為UNVISITED；當(dāng)vi已被訪問(wèn)，則tag值為VISITED。

一、圖的遍歷TraversingGraph3圖的遍歷與樹(shù)的遍歷有什么不同？

有兩種遍歷方法（它們對(duì)無(wú)向圖，有向圖都適用）深度優(yōu)先遍歷Depth_FirstSearch

廣度優(yōu)先遍歷Breadth_FirstSearch一、圖的遍歷4一、圖的遍歷算法：從圖中某頂點(diǎn)v出發(fā)：（1）訪問(wèn)頂點(diǎn)v；

（2）依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷；1、深度優(yōu)先遍歷5深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5

V5一、圖的遍歷6深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8

V8一、圖的遍歷7深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1V2

V2V4

V4V5V8一、圖的遍歷8深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V1V3V2V4V5V6V7V8

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V7一、圖的遍歷9template<classElemType>voidDFSTraverse(constAdjMatrixDirGraph<ElemType>&g,void(*Visit)(constElemType&)){ intv; for(v=0;v<g.GetVexNum();v++) { g.SetTag(v,UNVISITED); } for(v=0;v<g.GetVexNum();v++) { if(g.GetTag(v)==UNVISITED) DFS<ElemType>(g,v,Visit); }}圖的深度優(yōu)先遍歷算法10template<classElemType>voidDFS(constAdjMatrixDirGraph<ElemType>&g,intv,void(*Visit)(constElemType&)){ g.SetTag(v,VISITED); ElemTypee=g.GetVexData(v); Visit(e); for(intw=g.FirstAdjVex(v);w!=-1; w=g.NextAdjVex(v,w)) {if(g.GetTag(w)==UNVISITED) { DFS<ElemType>(g,w,Visit); } }}圖的深度優(yōu)先遍歷算法11一、圖的遍歷

A

H

G

F

E

D

C

B圖的深度優(yōu)先遍歷算法

01234567ABCDEFGH12673011045362523412算法分析圖中有n個(gè)頂點(diǎn)，e條邊。如果用鄰接表表示圖，沿adjLink鏈到next鏈可以找到某個(gè)頂點(diǎn)v的所有鄰接頂點(diǎn)w。由于總共有2e個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為O(e)。而且對(duì)所有頂點(diǎn)遞歸訪問(wèn)1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。13考研題分析有向圖的鄰接表如下，要求（1）畫(huà)出其鄰接矩陣存儲(chǔ)；（2）寫(xiě)出圖的所有強(qiáng)連同分量；（3）寫(xiě)出頂點(diǎn)a到頂點(diǎn)i的全部簡(jiǎn)單路徑；（4）寫(xiě)出以A為出發(fā)點(diǎn)開(kāi)始深度優(yōu)先遍歷得到的頂點(diǎn)序列。

123456789ABEDHICGF27634528739614考研題分析已知一個(gè)有向圖如下，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷，不可能夠得到的DFS序列為？AadbefcBadcefbCadcbfeDadefbcacefdb15一、圖的遍歷算法：從圖中某未訪問(wèn)過(guò)的頂點(diǎn)vi出發(fā)：（1）訪問(wèn)頂點(diǎn)vi；（2）訪問(wèn)vi的所有未被訪問(wèn)的鄰接點(diǎn)w1,w2,…wk

；（3）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn);依此類(lèi)推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；2、廣度優(yōu)先遍歷（類(lèi)似于樹(shù)的層次遍歷）16為實(shí)現(xiàn)(3)，需要保存在步驟(2)中訪問(wèn)的頂點(diǎn)，而且訪問(wèn)這些頂點(diǎn)鄰接點(diǎn)的順序?yàn)椋合缺４娴捻旤c(diǎn)，其鄰接點(diǎn)先被訪問(wèn)。一、圖的遍歷2、廣度優(yōu)先遍歷在廣度優(yōu)先遍歷算法中，需設(shè)置一隊(duì)列Q，保存已訪問(wèn)的頂點(diǎn)，并控制遍歷頂點(diǎn)的順序。

V1

V8

V7

V6

V5

V4

V3

V217廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1一、圖的遍歷18廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3一、圖的遍歷19廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5一、圖的遍歷20廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7一、圖的遍歷21廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8一、圖的遍歷22template<classElemType>voidBFSTraverse(constAdjListDirGraph<ElemType>&g,void(*Visit)(constElemType&)){ intv; for(v=0;v<g.GetVexNum();v++) { g.SetTag(v,UNVISITED); } for(v=0;v<g.GetVexNum();v++) { if(g.GetTag(v)==UNVISITED) { BFS<ElemType>(g,v,Visit); } }}圖的廣度優(yōu)先遍歷算法23template<classElemType>voidBFS(constAdjListDirGraph<ElemType>&g,intv,void(*Visit)(constElemType&)){ g.SetTag(v,VISITED); ElemTypee; g.GetElem(v,e); Visit(e); LinkQueue<int>q; q.InQueue(v);

圖的廣度優(yōu)先遍歷算法24 while(!q.Empty()) { //隊(duì)列q非空,進(jìn)行循環(huán) intu,w; q.OutQueue(u); for(w=g.FirstAdjVex(v);w>=0;w=g.NextAdjVex(v,w)) { if(g.GetTag(w)==UNVISITED) { g.SetTag(w,VISITED); g.GetElem(w,e); Visit(e); q.InQueue(w); } }}}圖的廣度優(yōu)先遍歷算法25

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

V4深度優(yōu)先遍歷廣度優(yōu)先遍歷兩種遍歷的比較一、圖的遍歷兩者遍歷的時(shí)間復(fù)雜度相同，不同之處僅僅在于對(duì)頂點(diǎn)訪問(wèn)的順序。26二、圖的連通性問(wèn)題無(wú)向圖的連通分量和生成樹(shù)

生成樹(shù)是一個(gè)連通圖G的一個(gè)極小的連通子圖。包含圖G的所有頂點(diǎn)，但只有n-1條邊，并且是連通的。生成樹(shù)可由遍歷過(guò)程中所經(jīng)過(guò)的邊組成。深度優(yōu)先遍歷得到的生成樹(shù)稱(chēng)為深度優(yōu)先生成樹(shù)；廣度優(yōu)先遍歷得到的生成樹(shù)稱(chēng)為廣度優(yōu)先生成樹(shù)。生成森林：非連通圖每個(gè)連通分量的生成樹(shù)一起組成非連通圖的生成森林。27V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹(shù)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V828ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林例29二、圖的連通性問(wèn)題說(shuō)明一個(gè)圖可以有許多棵不同的生成樹(shù)所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹(shù)是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹(shù)中再加一條邊必然形成回路

含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)1、生成樹(shù)和生成森林GHKI30

要在n個(gè)城市間建立交通網(wǎng)，要考慮的問(wèn)題如何在保證n點(diǎn)連通的前題下最節(jié)省經(jīng)費(fèi)?V2V0V3V5V4

求解:連通6個(gè)城市且代價(jià)最小的交通線路?如何求連通圖的最小生成樹(shù)?？

若有一個(gè)連通的無(wú)向圖G，有n個(gè)頂點(diǎn)，并且它的邊是有權(quán)值的。在G上構(gòu)造生成樹(shù)G’,最小生成樹(shù)是n-1條邊的權(quán)值之和最小的G’

。二、圖的連通性問(wèn)題31①普里姆算法Prim②克魯斯卡爾算法Kruskal二、圖的連通性問(wèn)題2、最小代價(jià)生成樹(shù)MinimumCostSpanningTree32例1654328613688526131163151643152116432152616543215263①普里姆算法Prim33

普里姆算法基本步驟設(shè)N=（V，E）為一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)的連通網(wǎng)絡(luò)，T=（U，TE）為構(gòu)造的生成樹(shù)。

(1)初始時(shí)，U={U0}，TE={}；

(2)在所有u

U、v

V-U的邊(u,v)E中選擇一條權(quán)值最小的邊(u0,v0)；

(3)(u0,v0)加入集合TE，同時(shí)將v0加入U(xiǎn)；

(4)重復(fù)(2)、(3)，直到U=V為止；二、圖的連通性問(wèn)題34abcdegf195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和=14+8+3+5+16+21=67再如：35template<classElemType,classWeightType>voidMiniSpanTreePrim(constAdjMatrixUndirNetwork<ElemType,WeightType>&net,intu0){ if(u0<0||u0>=net.GetVexNum())

throwError(“u0不合法1!”);

//拋出異常

int*adjVex;

intu,v,w;

adjVex=newint[net.GetVexNum()];

//分配存儲(chǔ)空間

普魯姆算法adjVex數(shù)組用于存儲(chǔ)V-U中的頂點(diǎn)到U最小權(quán)值的邊當(dāng)vV-U時(shí),adjVex[v]U,且<v,adjVex[v]>是v到U的最小權(quán)值邊0123456adjVex數(shù)組36 for(v=0;v<net.GetVexNum();v++) {//初始化輔助數(shù)組adjVex，并對(duì)頂點(diǎn)作標(biāo)志，此時(shí)U={u0} if(v!=u0) { //對(duì)于v∈V-U adjVex[v]=u0; net.SetTag(v,UNVISITED); } else { //對(duì)于v∈U net.SetTag(v,VISITED); adjVex[v]=u0; } }

普魯姆算法37adjVex0123456net.tag000000010000001:VISITED0:UNVISITEDU0=038for(u=1;u<net.GetVexNum();u++){ w=MinVertex(net,adjVex); if(w==-1) return; cout<<"edge:("<<adjVex[w]<<","<<w<<")weight:"<<net.GetWeight(w,adjVex[w])<<endl; net.SetTag(w,VISITED);

for(intv=net.FirstAdjVex(w);v>=0;v=net.NextAdjVex(w,v)) { if(net.GetTag(v)==UNVISITED&& (net.GetWeight(v,w)<net.GetWeight(v,adjVex[v])|| net.GetWeight(v,adjVex[v])==0)) { adjVex[v]=w; } }}delete[]adjVex; //釋放存儲(chǔ)空間}39template<classElemType,classWeightType>intMinVertex(constAdjMatrixUndirNetwork<ElemType,WeightType>&net,int*adjVex) { intw=-1; intv; for(v=0;v<net.GetVexNum();v++) { //查找第一個(gè)滿足條件的V-U中頂點(diǎn)v if(net.GetTag(v)==UNVISITED &&net.GetWeight(v,adjVex[v])>0) { w=v; break; } }

普魯姆算法40for(v++;v<net.GetVexNum();v++) if(net.GetTag(v)==UNVISITED&&net.GetWeight(v,adjVex[v])>0&& net.GetWeight(v,adjVex[v])<net.GetWeight(w,adjVex[w])) w=v; returnw;}

普魯姆算法41

克魯斯卡爾算法二、圖的連通性問(wèn)題Kruskal的基本思想：設(shè)有一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn),沒(méi)有邊的非連通圖T={V,

},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選到一條具有最小權(quán)值的邊,若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點(diǎn)在同一個(gè)連通分量上為止。42應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程5046132281025142422161812原圖二、圖的連通性問(wèn)題

克魯斯卡爾算法5046132(a)105046132(b)43504612281025142422161812原圖3(f)50461321014221612504613210141612(e)5046121025142216123(g)10125046132(c)5046132101412(d)441.初始化：U=V；TE={}；2.循環(huán)直到T中的連通分量個(gè)數(shù)為12.1在E中尋找最短邊(u，v);2.2如果頂點(diǎn)u、v位于T的兩個(gè)不同連通分量，則

2.2.1將邊(u，v)并入TE；

2.2.2將這兩個(gè)連通分量合為一個(gè)；

2.3在E中標(biāo)記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選??；Kruskal算法——偽代碼二、圖的連通性問(wèn)題作業(yè):請(qǐng)編程用克魯斯卡爾算法求最小生成樹(shù)。45Prim與Kruskal算法的性能比較:

(1)時(shí)間復(fù)雜性:Prim:O(n*n)Kruskal:O(eloge)(2)適用場(chǎng)合:Prim:稠密圖

Kruskal:稀疏圖

二、圖的連通性問(wèn)題46【ACM】【ZOJ1406】最小生成樹(shù)問(wèn)題【問(wèn)題描述】47如上圖所示，給出結(jié)點(diǎn)數(shù)量N，以及每個(gè)結(jié)點(diǎn)到相鄰結(jié)點(diǎn)的距離，要求給出一條最短連通路徑，連通所有結(jié)點(diǎn)（結(jié)點(diǎn)的字