第15講圖的遍歷

1EssentialofLectureFifteen

：

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

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

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

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

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

（2）依次從v的未被訪問的鄰接點(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(const

AdjMatrixDirGraph<ElemType>&g,void(*Visit)(const

ElemType&)){ 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(const

AdjMatrixDirGraph<ElemType>&g,intv,void(*Visit)(const

ElemType&)){

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)遞歸訪問1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。13考研題分析有向圖的鄰接表如下，要求（1）畫出其鄰接矩陣存儲(chǔ)；（2）寫出圖的所有強(qiáng)連同分量；（3）寫出頂點(diǎn)a到頂點(diǎn)i的全部簡(jiǎn)單路徑；（4）寫出以A為出發(fā)點(diǎn)開始深度優(yōu)先遍歷得到的頂點(diǎn)序列。

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

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

AdjListDirGraph<ElemType>&g,void(*Visit)(const

ElemType&)){

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)訪問的順序。26二、圖的連通性問題無向圖的連通分量和生成樹

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

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

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

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

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

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

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

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

(2)在所有uU

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

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

(4)重復(fù)(2)、(3)，直到U=V為止；二、圖的連通性問題34abcdegf195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67再如：35

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

克魯斯卡爾算法5046132(a)105046132(b)37504612281025142422161812原圖3(f)50461321014221612504613210141612(e)5046121025142216123(g)10125046132(c)5046132101412(d)381.初始化：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算法——偽代碼二、圖的連通性問題39Prim與Kruskal算法的性能比較:

(1)時(shí)間復(fù)雜性:Prim:O(n*n)

Kruskal:O(eloge)(2)適用場(chǎng)合:Prim:稠密圖

Kruskal:稀疏圖

二、圖的連通性問題40【ACM】【ZOJ1406】最小生成樹問題【問題描述】41如上圖所示，給出結(jié)點(diǎn)數(shù)量N，以及每個(gè)結(jié)點(diǎn)到相鄰結(jié)點(diǎn)的距離，要求給出一條最短連通路徑，連通所有結(jié)點(diǎn)（結(jié)點(diǎn)的字母不重復(fù)，個(gè)數(shù)不超過26個(gè)）。根據(jù)上圖我們可以給出如下一組數(shù)據(jù)：

9A2B12I25B3C10H40I8C2D18G55D1E44E2F60G38F0G1H35H1I35第一