圖的遍歷課件

1EssentialofLectureFifteen

：

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

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

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

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

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

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

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

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

V1

V8

V7

V6

V5

V4

V3

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

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

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

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

含n個頂點n-1條邊的圖不一定是生成樹1、生成樹和生成森林GHKI29二、圖的連通性問題說明1、生成樹和生成森林GHKI30

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

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

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

。二、圖的連通性問題30

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

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

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

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

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

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

克魯斯卡爾算法二、圖的連通性問題Kruskal的基本思想：設(shè)有一個有n個頂點的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個只有n個頂點,沒有邊的非連通圖T={V,},圖中每個頂點自成一個連通分量。在E中選到一條具有最小權(quán)值的邊,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點在同一個連通分量上為止。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中的連通分量個數(shù)為12.1在E中尋找最短邊(u，v);2.2如果頂點u、v位于T的兩個不同連通分量，則

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

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

2.3在E中標記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選取；Kruskal算法——偽代碼二、圖的連通性問題381.初始化：U=V；TE={}；Kruskal39Prim與Kruskal算法的性能比較:

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

Kruskal:稀疏圖

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

9A2B12I25B3C10H40I8C2D18G55D1E44E2F60G38F0G1H35H1I35第一行的9表示有9個結(jié)點，接下來共8行數(shù)據(jù)，每行數(shù)據(jù)給出該結(jié)點的名稱name，和相鄰結(jié)點數(shù)num，以及與相鄰結(jié)點X之間的距離Y。41如上圖所示，給出結(jié)點數(shù)量N，以及每個結(jié)點到相鄰結(jié)點的距離42

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

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

1、圖的深度、廣度遍歷

2、克魯斯卡爾算法難點：

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

：

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

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

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

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

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

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

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

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

V1

V8

V7

V6

V5

V4

V3

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

V0

V2

V3

V1

V5

V4

V0

V2

V3

V1

V5

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

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

含n個頂點n-1條邊的圖不一定是生成樹1、生成樹和生成森林GHKI29二、圖的連通性問題說明1、生成樹和生成森林GHKI76

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

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

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

。二、圖的連通性問題30

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

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

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

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

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

(4)重復(fù)(2)、(3)，直到U=V為止；二、圖的連通性問題33普里姆算法基本步驟二、圖的連通性問題80abcdegf195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67再如：34abcdegf195141827168213ae12dc81

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

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