最小生成樹(shù)與最短路徑問(wèn)題

圖——最小生成樹(shù)與最短路徑問(wèn)題2009/05/141基于鄰接表的圖操作運(yùn)算2基于鄰接表的圖操作運(yùn)算34主要內(nèi)容生成樹(shù)的概念（spanning

tree）Prim算法Kruskal算法最短路徑問(wèn)題Dijkstra算法Floyd算法

5生成樹(shù)（支撐樹(shù)）的概念GraphMatrixgraph={ 6, { {0,10,M,M,19,21}, {10,0,5,M,M,11}, {M,5,0,M,M,M}, {M,M,M,0,18,14}, {19,M,M,18,0,33}, {21,11,M,14,33,0} }};

0

1

2

3

4

5子圖+連通+無(wú)環(huán)6無(wú)向圖中無(wú)環(huán)的充要條件檢查每一個(gè)連通分枝對(duì)于所有連通分枝：頂點(diǎn)數(shù)–邊的數(shù)目=1可以采用周游算法。算法復(fù)雜度：n

0

1

2

3

4

57最小生成樹(shù)Minimum-costSpanningTree連通無(wú)向帶權(quán)圖——網(wǎng)絡(luò)。網(wǎng)絡(luò)（帶權(quán)圖）的生成樹(shù)中生成樹(shù)各邊的權(quán)值加起來(lái)稱為生成樹(shù)的權(quán)，把權(quán)值最小的生成樹(shù)稱為最小生成樹(shù)。(簡(jiǎn)稱為MST)。

8G=(V，E)是一個(gè)網(wǎng)絡(luò)，U是頂點(diǎn)集合V的一個(gè)真子集。如果u∈U，v∈V-U，且邊(u,v)是圖G中所有一個(gè)端點(diǎn)在U里，另一端點(diǎn)在V-U里的邊中權(quán)值最小的邊，則一定存在G的一棵最小生成樹(shù)包括此邊(u,v)。MST必包含連通圖中任意兩個(gè)頂點(diǎn)劃分之間的最小權(quán)的邊。（任意割集中的最小邊）MST性質(zhì)9MST性質(zhì)證明（反證法）uu′vv′UV-Uv

v邊(u,v)是圖G中所有一個(gè)端點(diǎn)在U里，另一端點(diǎn)在V-U里的邊中權(quán)值最小的邊。假設(shè)：存在G的一棵最小生成樹(shù)不包括此邊。10Prim算法（找MST）prim算法的基本思想是∶首先從集合V中任取一頂點(diǎn)(例如取頂點(diǎn)v0)放入集合U中這時(shí)U={v0}，TE=NULL然后在所有一個(gè)頂點(diǎn)在集合U里，另一個(gè)頂點(diǎn)在集合V-U里的邊中，找出權(quán)值最小的邊(u,v)(u∈U，v∈V-U)，將邊加入TE，并將頂點(diǎn)v加入集合U重復(fù)上述操作直到U=V為止。這時(shí)TE中有n-1條邊，T=(U，TE)就是G的一棵最小生成樹(shù)11最小生成樹(shù)的構(gòu)造準(zhǔn)備工作： 設(shè)圖采用鄰接矩陣表示法表示，用一對(duì)頂點(diǎn)的下標(biāo)(在頂點(diǎn)表中的下標(biāo))表示一條邊，定義如下∶在構(gòu)造最小生成樹(shù)的過(guò)程中定義一個(gè)類型為Edge的數(shù)組

mst∶Edgemst[n-1];

其中n為網(wǎng)絡(luò)中頂點(diǎn)的個(gè)數(shù)，算法結(jié)束時(shí)，mst中存放求出的最小生成樹(shù)的n-1條邊。typedefstruct{ intstart_vex,stop_vex;/*邊的起點(diǎn)和終點(diǎn)*/ AdjTypeweight; /*邊的權(quán)*/}Edge;12例子：mst∶Edgemst[n-1];已知帶權(quán)圖G及其鄰接矩陣如圖所示請(qǐng)構(gòu)造該圖的最小生成樹(shù)úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥033141121330181914180666051165010211910013n=6，只有頂點(diǎn)v0在最小生成樹(shù)中。

mst[5]={{0,1,10},{0,2,∞},{0,3,∞},{0,4,19},{0,5,21}}在mst[0]到mst[4]中找出權(quán)值最小的邊mst[0]，即(v0,v1)，將頂點(diǎn)v1及邊(v0,v1)加入最小生成樹(shù)。úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥03314112133018191418066605116501021191001n-114n=6，只有頂點(diǎn)v0在最小生成樹(shù)中。

mst[5]={{0,1,10},{0,2,∞},{0,3,∞},{0,4,19},{0,5,21}}在mst[0]到mst[4]中找出權(quán)值最小的邊mst[0]，即(v0,v1)，將頂點(diǎn)v1及邊(v0,v1)加入最小生成樹(shù)。調(diào)整：mst[5]={{0,1,10},{1,2,5},{1,3,6},{0,4,19},{1,5,11}}úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥03314112133018191418066605116501021191002n-2比較15mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},{1,5,11}}mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},{1,5,11}}úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥03314112133018191418066605116501021191003n-316mst[5]={{0,1,10},{1,2,5},{1,3,6},{1,5,11},{3,4,18}}17調(diào)整為成新邊18Prim算法時(shí)間復(fù)雜度Prim算法的時(shí)間主要花費(fèi)在選擇最小生成樹(shù)的n-1條邊上。外循環(huán)執(zhí)行n-1次，內(nèi)循環(huán)兩個(gè)，時(shí)間耗費(fèi)為：整個(gè)算法的時(shí)間復(fù)雜度為O(n2)19貪心算法一般思路初態(tài)（起點(diǎn)）候選對(duì)象集合貪心選擇算法（按當(dāng)前狀態(tài)）可行評(píng)估函數(shù)目標(biāo)函數(shù)20Kruskal算法設(shè)G=(V，E)是網(wǎng)絡(luò)，最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V，φ)，T中每個(gè)頂點(diǎn)自成為一個(gè)連通分量。將集合E中的邊按權(quán)遞增順序排列，從小到大依次選擇頂點(diǎn)分別在兩個(gè)不同連通分量中的邊加入圖T，則原來(lái)的兩個(gè)連通分量由于該邊的連接而成為一個(gè)連通分量。依次類推，直到T中所有頂點(diǎn)都在同一個(gè)連通分量上為止，該連通分量就是G的一棵最小生成樹(shù)。

21例題∶用Kruskal方法構(gòu)造圖的最小生成樹(shù)集合E中的邊按權(quán)遞增順序排列為∶

(v1,v25),(v1,v36),(v2,v36),(v0,v110),(v1,v511),(v3,v514),(v3,v418),(v0,v419),(v0,v521),(v4,v533)22

①初始時(shí)，T為只有6個(gè)頂點(diǎn)的非連通圖。②邊(v1,v2)的兩個(gè)頂點(diǎn)v1，v2分別屬于兩個(gè)連通分量，將邊(v1,v2)加入T。③同理，將邊(v1,v3)加入T。④由于邊(v2,v3)的兩個(gè)頂點(diǎn)v2，v3屬于同一個(gè)連通分量，因此，舍去這條邊。⑤同理將邊(v0,v1)、(v1,v5)加入T，邊(v3,v5)舍去，邊(v3,v4)加入T。這時(shí)T中含的邊數(shù)為5條，成為一個(gè)連通分量，T就是G的一棵最小生成樹(shù)。2324算法框架T=(V,φ)

while(T中所含邊數(shù)<n-1)

{

從E中選取當(dāng)前最短邊(u,v)；

從E中刪去邊(u,v)；

if((u,v)加入T中后不產(chǎn)生回路)

將邊(u,v)加入T中；

}

25最短路徑問(wèn)題如果圖中從一個(gè)頂點(diǎn)可以到達(dá)另一個(gè)頂點(diǎn)，則稱這兩個(gè)頂點(diǎn)間存在一條路徑。從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)間可能存在多條路徑，而每條路徑上經(jīng)過(guò)的邊數(shù)并不一定相同。如果圖是一個(gè)帶權(quán)圖，則路徑長(zhǎng)度為路徑上各邊的權(quán)值的總和，兩個(gè)頂點(diǎn)間路徑長(zhǎng)度最短的那條路徑稱為兩個(gè)頂點(diǎn)間的最短路徑，其路徑長(zhǎng)度稱為最短路徑長(zhǎng)度。26Dijkstra算法

——SingleSource/AllDestinationsDijkstra算法求解從頂點(diǎn)v0出發(fā)到其它各頂點(diǎn)最短路徑。01234567SanFranciscoDenverChicagoBostonNewYorkMiamiNewOrleansLosAngeles300100080012001500140010009001700100025027基本思想設(shè)置一個(gè)集合U，存放已求出最短路徑的頂點(diǎn)，V-U是尚未確定最短路徑的頂點(diǎn)集合。每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值，集合U中頂點(diǎn)的距離值是從頂點(diǎn)v0到該頂點(diǎn)的最短路徑長(zhǎng)度；集合V-U中頂點(diǎn)的距離值是從頂點(diǎn)v0到該頂點(diǎn)的只包括集合U中頂點(diǎn)為中間頂點(diǎn)的最短路徑長(zhǎng)度。28初始狀態(tài)：集合U中只有頂點(diǎn)v0，頂點(diǎn)v0對(duì)應(yīng)的距離值為0，集合V-U中頂點(diǎn)vi的距離值為邊(v0,vi)(i=1,2,…,n-1)的權(quán)，如果v0和vi間無(wú)邊直接相連，則vi的距離值為∞。29處理框架：（1）在集合V-U中選擇距離值最小的頂點(diǎn)vmin加入集合U；（2）對(duì)集合V-U中各頂點(diǎn)的距離值進(jìn)行修正：如果加入頂點(diǎn)vmin為中間頂點(diǎn)后，使v0到vi的距離值比原來(lái)的距離值更小，則修改vi的距離值。（3）重復(fù)（1）（2）操作，直到從v0出發(fā)可以到達(dá)的所有頂點(diǎn)都在集合U中為止。30存儲(chǔ)結(jié)構(gòu)圖采用鄰接矩陣表示法，其中對(duì)角線元素初值均取0。算法中，將放入集合Ｕ中結(jié)點(diǎn)對(duì)應(yīng)的關(guān)系矩陣中對(duì)角線元素值修改為1；設(shè)置一個(gè)數(shù)組dist，dist[ｉ]用于存放v0到頂點(diǎn)vｉ的最短路徑及其最短路徑長(zhǎng)度（計(jì)算過(guò)程中為距離值）∶

ypedefstruct{ AdjTypelength; /*最短路徑長(zhǎng)度*/ intprevex; /*從v0到達(dá)vi(i=1,2,…n-1)的最短路徑上vi的前趨頂點(diǎn)*/}Path;Path*dist;31修正距離值的方法如果加入頂點(diǎn)vmin為中間頂點(diǎn)后

dist[i].length>dist[min].length+G.arcs[min][i]則將頂點(diǎn)vi的距離值改為dist[min].length+G.arcs[min][i]并修改路徑上vi的前趨頂點(diǎn)：dist[i].prevex=min32例子：初始狀態(tài)V={v0}結(jié)果di