最小生成樹與最短路徑問題

《最小生成樹與最短路徑問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、圖——最小生成樹與最短路徑問題2009/05/14基于鄰接表的圖操作運(yùn)算2基于鄰接表的圖操作運(yùn)算34主要內(nèi)容生成樹的概念（spanningtree）Prim算法Kruskal算法最短路徑問題Dijkstra算法Floyd算法5生成樹（支撐樹）的概念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}}};012345子圖+連通+無環(huán)6無向圖中無環(huán)的充要條件檢查每一個(gè)連通分枝對(duì)

2、于所有連通分枝：頂點(diǎn)數(shù)–邊的數(shù)目=1可以采用周游算法。算法復(fù)雜度：n0123457最小生成樹Minimum-costSpanningTree連通無向帶權(quán)圖——網(wǎng)絡(luò)。網(wǎng)絡(luò)（帶權(quán)圖）的生成樹中生成樹各邊的權(quán)值加起來稱為生成樹的權(quán)，把權(quán)值最小的生成樹稱為最小生成樹。(簡(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的一棵最小生成樹包括此邊(u,v)。MST必包含連通圖中任意兩個(gè)頂點(diǎn)劃分之間的最小權(quán)的邊。（任意割集中的最小邊）

3、MST性質(zhì)9MST性質(zhì)證明（反證法）uu′vv′UV-Uv?v邊(u,v)是圖G中所有一個(gè)端點(diǎn)在U里，另一端點(diǎn)在V-U里的邊中權(quán)值最小的邊。假設(shè)：存在G的一棵最小生成樹不包括此邊。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的一棵最小生成樹11最

4、小生成樹的構(gòu)造準(zhǔn)備工作：設(shè)圖采用鄰接矩陣表示法表示，用一對(duì)頂點(diǎn)的下標(biāo)(在頂點(diǎn)表中的下標(biāo))表示一條邊，定義如下∶在構(gòu)造最小生成樹的過程中定義一個(gè)類型為Edge的數(shù)組mst∶Edgemst[n-1];其中n為網(wǎng)絡(luò)中頂點(diǎn)的個(gè)數(shù)，算法結(jié)束時(shí)，mst中存放求出的最小生成樹的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)造該圖的最小生成樹úúúúúúúú?ùêêêêêêêê?é

5、￥￥￥￥￥￥￥￥￥￥033141121330181914180666051165010211910013n=6，只有頂點(diǎn)v0在最小生成樹中。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)加入最小生成樹。úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥03314112133018191418066605116501021191001n-114n=6，只有頂點(diǎn)v0在最小生成樹中。mst[5

6、]={{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)加入最小生成樹。調(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},

7、{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)在選擇最小生成樹的n-1條邊上。外循環(huán)執(zhí)行n-1次，內(nèi)循環(huán)兩個(gè)，時(shí)間耗費(fèi)為：整個(gè)算法的時(shí)間復(fù)雜度為O(n2)19貪心算法

8、一般思路初態(tài)（起點(diǎn)）候選對(duì)象集合貪心選擇算法（按當(dāng)前狀態(tài)）可行評(píng)估