第15講圖的遍歷

1EssentialofLectureFifteen

：

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

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

一、圖的遍歷TraversingGraph3圖的遍歷與樹的遍歷有什么不同？

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

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

（2）依次從v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(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個頂點，e條邊。如果用鄰接表表示圖，沿adjLink鏈到next鏈可以找到某個頂點v的所有鄰接頂點w。由于總共有2e個邊結(jié)點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。13考研題分析有向圖的鄰接表如下，要求（1）畫出其鄰接矩陣存儲；（2）寫出圖的所有強連同分量；（3）寫出頂點a到頂點i的全部簡單路徑；（4）寫出以A為出發(fā)點開始深度優(yōu)先遍歷得到的頂點序列。

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

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

V1

V8

V7

V6

V5

V4

V3

V217廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1一、圖的遍歷18廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3一、圖的遍歷19廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5一、圖的遍歷20廣度優(yōu)先遍歷序列?入隊序列?出隊序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7一、圖的遍歷21廣度優(yōu)先遍歷序列?入隊序列?出隊序列?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()) { //隊列q非空,進行循環(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)先遍歷兩種遍歷的比較一、圖的遍歷兩者遍歷的時間復(fù)雜度相同，不同之處僅僅在于對頂點訪問的順序。26二、圖的連通性問題無向圖的連通分量和生成樹

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

含n個頂點n-1條邊的圖不一定是生成樹1、生成樹和生成森林GHKI30

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

求解:連通6個城市且代價最小的交通線路?如何求連通圖的最小生成樹?？

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

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

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

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

(2)在所有u

U、v

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

(3)(u0,v0)加入集合TE，同時將v0加入U；

(4)重復(fù)(2)、(3)，直到U=V為止；二、圖的連通性問題34abcdegf195141827168213ae12dcbgf7148531621所得生成樹權(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()];

//分配存儲空間

普魯姆算法adjVex數(shù)組用于存儲V-U中的頂點到U最小權(quán)值的邊當(dāng)vV-U時,adjVex[v]U,且<v,adjVex[v]>是v到U的最小權(quán)值邊0123456adjVex數(shù)組36 for(v=0;v<net.GetVexNum();v++) {//初始化輔助數(shù)組adjVex，并對頂點作標(biāo)志，此時U={u0} if(v!=u0) { //對于v∈V-U adjVex[v]=u0; net.SetTag(v,UNVISITED); } else { //對于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; //釋放存儲空間}39template<classElemType,classWeightType>intMinVertex(constAdjMatrixUndirNetwork<ElemType,WeightType>&net,int*adjVex) { intw=-1; intv; for(v=0;v<net.GetVexNum();v++) { //查找第一個滿足條件的V-U中頂點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

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

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

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

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

2.2.2將這兩個連通分量合為一個；

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

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

Kruskal:稀疏圖

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