資源描述：
《最小生成樹與最短路徑問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、圖——最小生成樹與最短路徑問題2009/05/14基于鄰接表的圖操作運算2基于鄰接表的圖操作運算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)的充要條件檢查每一個連通分枝對
2、于所有連通分枝：頂點數(shù)–邊的數(shù)目=1可以采用周游算法。算法復雜度：n0123457最小生成樹Minimum-costSpanningTree連通無向帶權(quán)圖——網(wǎng)絡。網(wǎng)絡（帶權(quán)圖）的生成樹中生成樹各邊的權(quán)值加起來稱為生成樹的權(quán)，把權(quán)值最小的生成樹稱為最小生成樹。(簡稱為MST)。8G=(V，E)是一個網(wǎng)絡，U是頂點集合V的一個真子集。如果u∈U，v∈V-U，且邊(u,v)是圖G中所有一個端點在U里，另一端點在V-U里的邊中權(quán)值最小的邊，則一定存在G的一棵最小生成樹包括此邊(u,v)。MST必包含連通圖中任意兩個頂點劃分之間的最小權(quán)的邊。（任意割集中的最小邊）
3、MST性質(zhì)9MST性質(zhì)證明（反證法）uu′vv′UV-Uv?v邊(u,v)是圖G中所有一個端點在U里，另一端點在V-U里的邊中權(quán)值最小的邊。假設：存在G的一棵最小生成樹不包括此邊。10Prim算法（找MST）prim算法的基本思想是∶首先從集合V中任取一頂點(例如取頂點v0)放入集合U中這時U={v0}，TE=NULL然后在所有一個頂點在集合U里，另一個頂點在集合V-U里的邊中，找出權(quán)值最小的邊(u,v)(u∈U，v∈V-U)，將邊加入TE，并將頂點v加入集合U重復上述操作直到U=V為止。這時TE中有n-1條邊，T=(U，TE)就是G的一棵最小生成樹11最
4、小生成樹的構(gòu)造準備工作：設圖采用鄰接矩陣表示法表示，用一對頂點的下標(在頂點表中的下標)表示一條邊，定義如下∶在構(gòu)造最小生成樹的過程中定義一個類型為Edge的數(shù)組mst∶Edgemst[n-1];其中n為網(wǎng)絡中頂點的個數(shù)，算法結(jié)束時，mst中存放求出的最小生成樹的n-1條邊。typedefstruct{intstart_vex,stop_vex;/*邊的起點和終點*/AdjTypeweight;/*邊的權(quán)*/}Edge;12例子：mst∶Edgemst[n-1];已知帶權(quán)圖G及其鄰接矩陣如圖所示請構(gòu)造該圖的最小生成樹úúúúúúúú?ùêêêêêêêê?é
5、￥￥￥￥￥￥￥￥￥￥033141121330181914180666051165010211910013n=6，只有頂點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)，將頂點v1及邊(v0,v1)加入最小生成樹。úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥03314112133018191418066605116501021191001n-114n=6，只有頂點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)，將頂點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算法時間復雜度Prim算法的時間主要花費在選擇最小生成樹的n-1條邊上。外循環(huán)執(zhí)行n-1次，內(nèi)循環(huán)兩個，時間耗費為：整個算法的時間復雜度為O(n2)19貪心算法
8、一般思路初態(tài)（起點）候選對象集合貪心選擇算法（按當前狀態(tài)）可行評估
