圖的遍歷課件

1EssentialofLectureFifteen

：

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

圖的遍歷：從圖的某頂點(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。

一、圖的遍歷TraversingGraph2 圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問圖中所有頂點(diǎn)，并且每個(gè)頂3圖的遍歷與樹的遍歷有什么不同？

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

廣度優(yōu)先遍歷Breadth_FirstSearch一、圖的遍歷3圖的遍歷與？有兩種遍歷方法（它們對(duì)無(wú)向圖，有向圖都適4一、圖的遍歷算法：從圖中某頂點(diǎn)v出發(fā)：（1）訪問頂點(diǎn)v；

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

V1遍歷序列：V1V2

V2V4

V4V5

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

V1遍歷序列：V1V2

V2V4

V4V5V8

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

V1遍歷序列：V1V2

V2V4

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

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V7一、圖的遍歷8深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V9template<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)先遍歷算法9template<classElemType>圖的深度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)先遍歷算法10template<classElemType>圖的深11一、圖的遍歷

A

H

G

F

E

D

C

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

01234567ABCDEFGH12673011045362523411一、圖的遍歷AHGFEDCB圖的深度優(yōu)先12算法分析圖中有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)。12算法分析圖中有n個(gè)頂點(diǎn)，e條邊。13考研題分析有向圖的鄰接表如下，要求（1）畫出其鄰接矩陣存儲(chǔ)；（2）寫出圖的所有強(qiáng)連同分量；（3）寫出頂點(diǎn)a到頂點(diǎn)i的全部簡(jiǎn)單路徑；（4）寫出以A為出發(fā)點(diǎn)開始深度優(yōu)先遍歷得到的頂點(diǎn)序列。

123456789ABEDHICGF27634528739613考研題分析有向圖的鄰接表如下，要求（1）畫出其鄰接矩陣存14考研題分析已知一個(gè)有向圖如下，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷，不可能夠得到的DFS序列為？AadbefcBadcefbCadcbfeDadefbcacefdb14考研題分析已知一個(gè)有向圖如下，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先15一、圖的遍歷算法：從圖中某未訪問過的頂點(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)先遍歷（類似于樹的層次遍歷）15一、圖的遍歷算法：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

V216為實(shí)現(xiàn)(3)，需要保存在步驟(2)中訪問的頂點(diǎn)，而且訪問17廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1一、圖的遍歷17廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V18廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3一、圖的遍歷18廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V19廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5一、圖的遍歷19廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V20廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7一、圖的遍歷20廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V21廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8一、圖的遍歷21廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V22template<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)先遍歷算法22template<classElemType>圖的廣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)先遍歷算法23template<classElemType>圖的廣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)先遍歷算法24 while(!q.Empty())圖的廣度優(yōu)先遍歷算25

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

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

生成樹是一個(gè)連通圖G的一個(gè)極小的連通子圖。包含圖G的所有頂點(diǎn)，但只有n-1條邊，并且是連通的。生成樹可由遍歷過程中所經(jīng)過的邊組成。深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的生成森林。26二、圖的連通性問題無(wú)向圖的連通分量和生成樹27V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V827V1V2V4V5V3V7V6V8例深度遍歷：V1V228ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林例28ABLMCFDEGHKIJABLMCFJDEGHKI深度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、生成樹和生成森林GHKI29二、圖的連通性問題說明1、生成樹和生成森林GHKI30

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

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

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

。二、圖的連通性問題30

要在n個(gè)城市間建立交通網(wǎng)，要考慮的問題如31①普里姆算法Prim②克魯斯卡爾算法Kruskal二、圖的連通性問題2、最小代價(jià)生成樹MinimumCostSpanningTree31①普里姆算法Prim二、圖的連通性問題2、最小代價(jià)生32例1654328613688526131163151643152116432152616543215263①普里姆算法Prim32例16543286136885261311631516433

普里姆算法基本步驟設(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為止；二、圖的連通性問題33普里姆算法基本步驟二、圖的連通性問題34abcdegf195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67再如：34abcdegf195141827168213ae12dc35

克魯斯卡爾算法二、圖的連通性問題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è)連通分量上為止。35克魯斯卡爾算法二、圖的連通性問題Kruskal的基本36應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程5046132281025142422161812原圖二、圖的連通性問題

克魯斯卡爾算法5046132(a)105046132(b)36應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程50461322837504612281025142422161812原圖3(f)50461321014221612504613210141612(e)5046121025142216123(g)10125046132(c)5046132101412(d)37504612281025142422161812原圖3(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ù)最短邊的選?。籏ruskal算法——偽代碼二、圖的連通性問題381.初始化：U=V；TE={}；Kruskal39Prim與Kruskal算法的性能比較:

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

Kruskal:稀疏圖

二、圖的連通性問題39Prim與Kruskal算法的性能比較:二、圖的連通性問40【ACM】【ZOJ1406】最小生成樹問題【問題描述】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第一行的9表示有9個(gè)結(jié)點(diǎn)，接下來共8行數(shù)據(jù)，每行數(shù)據(jù)給出該結(jié)點(diǎn)的名稱name，和相鄰結(jié)點(diǎn)數(shù)num，以及與相鄰結(jié)點(diǎn)X之間的距離Y。41如上圖所示，給出結(jié)點(diǎn)數(shù)量N，以及每個(gè)結(jié)點(diǎn)到相鄰結(jié)點(diǎn)的距離42

不難發(fā)現(xiàn)，每行結(jié)點(diǎn)只給出了結(jié)點(diǎn)名稱大于該結(jié)點(diǎn)的相鄰結(jié)點(diǎn)的距離。比如B與A相鄰，且距離為12。在第一行A“結(jié)點(diǎn)信息表”中給出了A到B的距離12，但在第二行B“結(jié)點(diǎn)信息表”中就不必給出小于字母B的A結(jié)點(diǎn)的信息（為了避免數(shù)據(jù)冗余）。所以最后一個(gè)結(jié)點(diǎn)I，沒有比它字母再大的結(jié)點(diǎn)，故省略該行。

要求最后得出一條最短連通路徑，把該路徑長(zhǎng)度輸出，在本例中路徑長(zhǎng)度為216（如右圖所示）。下面現(xiàn)場(chǎng)用克魯斯卡爾算法實(shí)現(xiàn)42不難發(fā)現(xiàn)，每行結(jié)點(diǎn)只給出了結(jié)點(diǎn)名稱大于該結(jié)點(diǎn)的相鄰結(jié)43【ACM】【POJ2168】有向圖的強(qiáng)連通分量題意：有一群牛，總數(shù)為N(N<=10000),題目數(shù)據(jù)給出牛之間的關(guān)系，比如1仰慕2，2仰慕3等等，設(shè)這種仰慕是可以傳遞的，如果1仰慕2，那么1也會(huì)同時(shí)仰慕2仰慕的那些牛，如果一頭牛被所有的牛都仰慕，那么它將是最受歡迎的牛，題目要求的是有多少牛是"最受歡迎的"。43【ACM】【POJ2168】題意：有一群牛，總數(shù)為N(44在同一個(gè)強(qiáng)連通分量里的所有的牛之間是互相仰慕的，我們將其縮為一點(diǎn)，并且只記錄這一點(diǎn)的牛的數(shù)量，如果有最受歡迎的牛存在，那么這個(gè)圖將是連通圖，并且出度為零的點(diǎn)只有一個(gè)，我們需要判斷是否連通，然后計(jì)算每個(gè)節(jié)點(diǎn)的出度，即可求出最受歡迎的牛的數(shù)量。請(qǐng)有興趣的同學(xué)試著寫一寫。44在同一個(gè)強(qiáng)連通分量里的所有的牛之間是互相仰慕的，我們將其45本講小結(jié)重點(diǎn)：

1、圖的深度、廣度遍歷

2、克魯斯卡爾算法難點(diǎn)：

1、普里姆算法45本講小結(jié)重點(diǎn)：46對(duì)下面的連通圖，分別用Prim和Kruskal算法構(gòu)造其最小生成樹，后者給出圖解過程。1238765422221111243seeyoulater!46對(duì)下面的連通圖，分別用Prim和Kruskal算法構(gòu)造其47EssentialofLectureFifteen

：

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

圖的遍歷：從圖的某頂點(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。

一、圖的遍歷TraversingGraph2 圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問圖中所有頂點(diǎn)，并且每個(gè)頂49圖的遍歷與樹的遍歷有什么不同？

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

廣度優(yōu)先遍歷Breadth_FirstSearch一、圖的遍歷3圖的遍歷與？有兩種遍歷方法（它們對(duì)無(wú)向圖，有向圖都適50一、圖的遍歷算法：從圖中某頂點(diǎn)v出發(fā)：（1）訪問頂點(diǎn)v；

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

V1遍歷序列：V1V2

V2V4

V4V5

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

V1遍歷序列：V1V2

V2V4

V4V5V8

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

V1遍歷序列：V1V2

V2V4

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

V1遍歷序列：V1

V7V2V4V5V8V3

V3V6

V6V7一、圖的遍歷8深一層遞歸遞歸返回深度優(yōu)先遍歷序列?入棧序列?出棧序列?V55template<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)先遍歷算法9template<classElemType>圖的深度56template<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)先遍歷算法10template<classElemType>圖的深57一、圖的遍歷

A

H

G

F

E

D

C

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

01234567ABCDEFGH12673011045362523411一、圖的遍歷AHGFEDCB圖的深度優(yōu)先58算法分析圖中有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)。12算法分析圖中有n個(gè)頂點(diǎn)，e條邊。59考研題分析有向圖的鄰接表如下，要求（1）畫出其鄰接矩陣存儲(chǔ)；（2）寫出圖的所有強(qiáng)連同分量；（3）寫出頂點(diǎn)a到頂點(diǎn)i的全部簡(jiǎn)單路徑；（4）寫出以A為出發(fā)點(diǎn)開始深度優(yōu)先遍歷得到的頂點(diǎn)序列。

123456789ABEDHICGF27634528739613考研題分析有向圖的鄰接表如下，要求（1）畫出其鄰接矩陣存60考研題分析已知一個(gè)有向圖如下，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷，不可能夠得到的DFS序列為？AadbefcBadcefbCadcbfeDadefbcacefdb14考研題分析已知一個(gè)有向圖如下，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先61一、圖的遍歷算法：從圖中某未訪問過的頂點(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)先遍歷（類似于樹的層次遍歷）15一、圖的遍歷算法：2、廣度優(yōu)先遍歷（類似于樹的層次遍歷）62為實(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

V216為實(shí)現(xiàn)(3)，需要保存在步驟(2)中訪問的頂點(diǎn)，而且訪問63廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V1一、圖的遍歷17廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V64廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V2V3V3一、圖的遍歷18廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V65廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V3V4V4V5V5一、圖的遍歷19廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V66廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V4V5V5V6V6V7V7一、圖的遍歷20廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V67廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V2V4V5V6V7V8遍歷序列：V1V2V3V4V5V5V6V6V7V7V8V8一、圖的遍歷21廣度優(yōu)先遍歷序列?入隊(duì)序列?出隊(duì)序列?V1V3V68template<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)先遍歷算法22template<classElemType>圖的廣69template<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)先遍歷算法23template<classElemType>圖的廣70 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)先遍歷算法24 while(!q.Empty())圖的廣度優(yōu)先遍歷算71

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

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

生成樹是一個(gè)連通圖G的一個(gè)極小的連通子圖。包含圖G的所有頂點(diǎn)，但只有n-1條邊，并且是連通的。生成樹可由遍歷過程中所經(jīng)過的邊組成。深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的生成森林。26二、圖的連通性問題無(wú)向圖的連通分量和生成樹73V1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V827V1V2V4V5V3V7V6V8例深度遍歷：V1V274ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林例28ABLMCFDEGHKIJABLMCFJDEGHKI深度75二、圖的連通性問題說明一個(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、生成樹和生成森林GHKI29二、圖的連通性問題說明1、生成樹和生成森林GHKI76

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

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

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

。二、圖的連通性問題30

要在n個(gè)城市間建立交通網(wǎng)，要考慮的問題如77①普里姆算法Prim②克魯斯卡爾算法Kruskal二、圖的連通性問題2、最小代價(jià)生成樹MinimumCostSpanningTree31①普里姆算法Prim二、圖的連通性問題2、最小代價(jià)生78例1654328613688526131163151643152116432152616543215263①普里姆算法Prim32例16543286136885261311631516479

普里姆算法基本步驟設(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為止；二、圖的連通性問題33普里姆算法基本步驟二、圖的連通性問題80abcdegf195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67再如：34abcdegf195141827168213ae12dc81

克魯斯卡爾算法二、圖的連通性問題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è)連通分量上為止。35克魯斯卡爾算法二、圖的連通性問題Kruskal的基本82應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程5046132281025142422161812原圖二、圖的連通性問題

克魯斯卡爾算法5046132(a)105046132(b)36應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程50461322883504612281025142422161812原圖3(f)50461321014221612504613210141612(e)50461210251422161