1、 圖圖 最小生成樹與最短路徑問題 2009/05/142基于鄰接表的圖操作運(yùn)算基于鄰接表的圖操作運(yùn)算3基于鄰接表的圖操作運(yùn)算基于鄰接表的圖操作運(yùn)算45主要內(nèi)容主要內(nèi)容 生成樹的概念（spanning tree） Prim算法 Kruskal算法 最短路徑問題 Dijkstra算法 Floyd算法6生成樹（支撐樹）的概念生成樹（支撐樹）的概念GraphMatrix graph = 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, 1

2、4, 33, 0; 0 1 2 3 4 5子圖子圖 + 連通連通 + 無環(huán)無環(huán)7無向圖中無環(huán)的充要條件無向圖中無環(huán)的充要條件 檢查每一個連通分枝 對于所有連通分枝： 頂點(diǎn)數(shù) 邊的數(shù)目 = 1可以采用周游算法。算法復(fù)雜度：n 0 1 2 3 4 58最小生成樹最小生成樹 Minimum-cost Spanning Tree 連通無向帶權(quán)圖 網(wǎng)絡(luò)。 網(wǎng)絡(luò)（帶權(quán)圖）的生成樹中生成樹各邊的權(quán)值加起來稱為生成樹的權(quán)生成樹的權(quán)，把權(quán)值最小的生成樹稱為最小生成樹。最小生成樹。 (簡稱為MST)。 9 G=(V，E)是一個網(wǎng)絡(luò)，U是頂點(diǎn)集合V的一個真子集。 如果uU，vV-U，且邊(u,v)是圖G中所有一個端

3、點(diǎn)在U里，另一端點(diǎn)在V-U里的邊中權(quán)值最小的邊， 則一定存在G的一棵最小生成樹包括此邊(u,v)。MST必包含連通圖中任意兩個頂點(diǎn)劃分之間的最小權(quán)的邊。（任意割集中的最小邊）MST性質(zhì)性質(zhì)10MST性質(zhì)證明（反證法）性質(zhì)證明（反證法）uuvvUV-Uvv邊(u,v)是圖G中所有一個端點(diǎn)在U里，另一端點(diǎn)在V-U里的邊中權(quán)值最小的邊。 假設(shè)：存在G的一棵最小生成樹不包括此邊。11Prim算法（找算法（找MST）prim算法的基本思想是算法的基本思想是 首先從集合V中任取一頂點(diǎn)(例如取頂點(diǎn)v0)放入集合U中這時U=v0，TE=NULL 然后在所有一個頂點(diǎn)在集合U里，另一個頂點(diǎn)在集合V-U里的邊中，找

4、出權(quán)值最小的邊(u,v)(uU，vV-U)，將邊加入TE，并將頂點(diǎn)v加入集合U 重復(fù)上述操作直到U=V為止。這時TE中有n-1條邊，T=(U，TE)就是G的一棵最小生成樹12最小生成樹的構(gòu)造最小生成樹的構(gòu)造準(zhǔn)備工作： 設(shè)圖采用鄰接矩陣表示法表示，用一對頂點(diǎn)的下標(biāo)(在頂點(diǎn)表中的下標(biāo))表示一條邊，定義如下 在構(gòu)造最小生成樹的過程中定義一個類型為Edge的數(shù)組 mst Edge mstn-1; 其中n為網(wǎng)絡(luò)中頂點(diǎn)的個數(shù)，算法結(jié)束時，mst中存放求出的最小生成樹的n-1條邊。typedef structint start_vex, stop_vex;/* 邊的起點(diǎn)和終點(diǎn) */AdjType weigh

5、t; /* 邊的權(quán) */Edge;13例子：例子：mst Edge mstn-1;已知帶權(quán)圖G及其鄰接矩陣如圖所示請構(gòu)造該圖的最小生成樹 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 033141121330181914180666051165010211910014 n=6，只有頂點(diǎn)v0在最小生成樹中。 mst5=0,1,10, 0,2, 0,3, 0,4,19, 0,5,21 在mst0到mst4中找出權(quán)值最小的邊mst0，即(v0, v1)，將頂點(diǎn)v1及邊(v0, v1)加入最小生成樹。 v0 10 v1 21 11 5 v5 19 33 14

6、 6 v2 6 v4 18 v3 03314112133018191418066605116501021191001n -115 n=6，只有頂點(diǎn)v0在最小生成樹中。 mst5=0,1,10, 0,2, 0,3, 0,4,19, 0,5,21 在mst0到mst4中找出權(quán)值最小的邊mst0，即(v0, v1)，將頂點(diǎn)v1及邊(v0, v1)加入最小生成樹。調(diào)整： mst5=0,1,10, 1,2,5, 1,3,6, 0,4,19, 1,5,11 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 033141121330181914180666051165

7、01021191002n -2比較16mst5=0,1,10, 1,2,5, 1,3,6, 3,4,18, 1,5,11 mst5=0,1,10, 1,2,5, 1,3,6, 3,4,18, 1,5,11 03314112133018191418066605116501021191003n -3 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 17mst5=0,1,10, 1,2,5, 1,3,6, 1,5,11 , 3,4,18 v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 18 v3 18調(diào)整為成新邊19Prim算法

8、時間復(fù)雜度算法時間復(fù)雜度 Prim算法的時間主要花費(fèi)在選擇最小生成樹的n-1條邊上。外循環(huán)執(zhí)行n-1次，內(nèi)循環(huán)兩個，時間耗費(fèi)為： 整個算法的時間復(fù)雜度為O(n2) 20221202)1(2) )1()1(ninijnijninijOOO20貪心算法一般思路貪心算法一般思路 初態(tài)（起點(diǎn)） 候選對象集合 貪心選擇算法（按當(dāng)前狀態(tài)） 可行評估函數(shù) 目標(biāo)函數(shù)21Kruskal算法 設(shè)G=(V，E)是網(wǎng)絡(luò)，最小生成樹的初始狀態(tài)為只有n個頂點(diǎn)而無邊的非連通圖T=(V，)，T中每個頂點(diǎn)自成為一個連通分量。 將集合E中的邊按權(quán)遞增順序排列，從小到大從小到大依次選擇頂點(diǎn)分別在兩個不同連通分量分別在兩個不同連通分

9、量中的邊加入圖T，則原來的兩個連通分量由于該邊的連接而成為一個連通分量。 依次類推，直到T中所有頂點(diǎn)都在同一個連通分量上為止，該連通分量就是G的一棵最小生成樹。22例題例題 用用Kruskal方法構(gòu)造圖的最小生成方法構(gòu)造圖的最小生成樹樹 集合E中的邊按權(quán)遞增順序排列為(v1, v2 5), (v1, v3 6), (v2, v3 6), (v0, v1 10), (v1, v5 11), (v3, v5 14), (v3, v4 18), (v0, v4 19), (v0, v5 21), (v4, v5 33) v0 10 v1 21 11 5 v5 19 33 14 6 v2 6 v4 1

10、8 v3 23初始時，T為只有6個頂點(diǎn)的非連通圖。邊(v1, v2)的兩個頂點(diǎn)v1，v2分別屬于兩個連通分量，將邊(v1, v2)加入T。同理，將邊(v1, v3)加入T。由于邊由于邊(v2, v3)的兩個頂點(diǎn)的兩個頂點(diǎn)v2，v3屬于同一個連通分量，因?qū)儆谕粋€連通分量，因此，舍去這條邊。此，舍去這條邊。同理將邊(v0, v1)、(v1, v5)加入T，邊(v3, v5)舍去，邊(v3, v4)加入T。這時T中含的邊數(shù)為5條，成為一個連通分量，T就是G的一棵最小生成樹。2425算法框架算法框架 T=(V,)while(T中所含邊數(shù) distmin.length + G.arcsmini 則將頂

11、點(diǎn)vi的距離值改為 distmin.length + G.arcsmini并修改路徑上vi的前趨頂點(diǎn)： disti.prevex = min33例子：例子： 初始狀態(tài)V = v0 結(jié)果distn為0, 0, 50, 0, 10, 0, MAX, -1, 45, 0, MAX, -1 34在集合V-U中找出距離值最小的頂點(diǎn)v2，將頂點(diǎn)v2加入集合U中。原：distn為0, 0, 50, 0, 10, 0, MAX, -1, 45, 0, MAX, -1 后：distn為0, 0, 50, 0, 10, 0, 25, 2, 45, 0, MAX, -1 35（接）同理在集合V-U中找出當(dāng)前距離值最

12、小的頂點(diǎn)v3，并調(diào)整集合V-U中頂點(diǎn)的距離值。原：distn為0, 0, 50, 0, 10, 0, 25, 2, 45, 0, MAX, -1 后：distn為0, 0, 45, 3, 10, 0, 25, 2, 45, 0, MAX, -1 36最后：最后： 在集合V-U中找出當(dāng)前距離值最小的頂點(diǎn)v4。并調(diào)整集合V-U中頂點(diǎn)的距離值。 結(jié)果distn為0, 0, 45, 3, 10, 0, 25, 2, 45, 0, MAX, -1 沒有可以再加入集合U的頂點(diǎn)了，說明從頂點(diǎn)v0到頂點(diǎn)v5之間無路徑相通。過程結(jié)束。37算法分析算法分析 算法中的初始化部分的時間復(fù)雜度為O(n)， 求最短路徑部

13、分由一個大循環(huán)組成，其中外循環(huán)運(yùn)行n-1次，內(nèi)循環(huán)為兩個，均運(yùn)行n-1次，因此，算法的時間復(fù)雜度為O(n2)。 另外需要注意，在算法中改變了關(guān)系矩陣中的初始狀態(tài)，如果要求算法不能破壞原始數(shù)據(jù)，就需要另外增加數(shù)據(jù)結(jié)構(gòu)記錄集合的值?？臻g代價是（） 38FloydFloyd算法算法 All pairs Shortest Paths 基本思想： 圖采用鄰接矩陣作為存儲結(jié)構(gòu)。把關(guān)系矩陣看成是沒有經(jīng)過任何中間結(jié)點(diǎn)，直接可以到達(dá)的每一對頂點(diǎn)間的最短路徑的完整表示， 然后經(jīng)過多次迭代，每次增加一個新的結(jié)點(diǎn)，在允許這個結(jié)點(diǎn)作為中間結(jié)點(diǎn)的條件下，計(jì)算每一對頂點(diǎn)間的最短路徑的縮短變化， 直到把所有結(jié)點(diǎn)都考慮進(jìn)去為止

14、，結(jié)果得到每一對頂點(diǎn)間的最短路徑。 39數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)typedef structAdjType *a; /*存放每對頂點(diǎn)間最短路徑長度 */int *nextvex; /*存放vi到vj最短路徑上vi的后繼頂點(diǎn)的下標(biāo)值 */ShortPath;*a: 存放每對頂點(diǎn)間的距離（或最短路徑長度） ， 以關(guān)系矩陣作為其初始狀態(tài)。*nextvex：存放vi到vj最短路徑上vi的后繼頂點(diǎn)的下標(biāo)值。以 保存全部最短路徑的軌跡，40例題例題 用Floyd方法求圖G10各頂點(diǎn)間的最短路徑長度。4103030350201502051504510500A0513111143111143111113210141211141210nextvex0