圖的連通性最小生成樹的算法思想

1、圖的連通性11.算法思想 假設N=(V,E) 是連通網(wǎng),TE是N上最小生成樹中邊的集合,算法從U=vk,TE= 開始(即從vk出發(fā)求最小生成樹,vkV)。重復執(zhí)行下述操作： 在所有的邊(vi,vj)E (viU,vjV-U)中尋找一條權值最小的邊(vi,vj)將其添加到TE中(或打印之),同時把vj添 加到集合U 中 。 反復執(zhí)行上述操作n-1次（或所有頂點全部加入U時為止）。 一、最小生成樹22.實例：V=v1,v2,v3,v4,v5,v6 一、最小生成樹v1v2v3v4v5v66551256463任取uk=v1, 則：U=v1,V-U=v2,v3,v4,v5,v6 32.實例：V=v1,v

2、2,v3,v4,v5,v6 一、最小生成樹v1v2v3v4v5v66551256463任取uk=v1, 則：U=v1,V-U=v2,v3,v4,v5,v6 取邊(v1,v3),則：U=v1,v3V-U=v2,v4,v5,v6 42.實例：V=v1,v2,v3,v4,v5,v6 一、最小生成樹v1v2v3v4v5v66551256463任取uk=v1, 則：U=v1,V-U=v2,v3,v4,v5,v6 取邊(v1,v3),則：U=v1,v3V-U=v2,v4,v5,v6 取邊(v3,v6),則：U=v1,v3, v6V-U=v2,v4,v5 52.實例：V=v1,v2,v3,v4,v5,v6

3、一、最小生成樹v1v2v3v4v5v66551256463任取uk=v1, 則：U=v1,V-U=v2,v3,v4,v5,v6 取邊(v1,v3),則：U=v1,v3V-U=v2,v4,v5,v6 取邊(v3,v6),則：U=v1,v3, v6V-U=v2,v4,v5 取邊(v6,v4),則：U=v1,v3, v6,v4V-U=v2,v5 62.實例：V=v1,v2,v3,v4,v5,v6 一、最小生成樹v1v2v3v4v5v66551256463任取uk=v1, 則：U=v1,V-U=v2,v3,v4,v5,v6 取邊(v1,v3),則：U=v1,v3V-U=v2,v4,v5,v6 取邊(v

4、3,v6),則：U=v1,v3, v6V-U=v2,v4,v5 取邊(v6,v4),則：U=v1,v3, v6,v4V-U=v2,v5 取邊(v3,v2),則：U=v1,v3, v6,v4,v2V-U=v5 72.實例：V=v1,v2,v3,v4,v5,v6 一、最小生成樹v1v2v3v4v5v66551256463任取uk=v1, 則：U=v1,V-U=v2,v3,v4,v5,v6 取邊(v1,v3),則：U=v1,v3V-U=v2,v4,v5,v6 取邊(v3,v6),則：U=v1,v3, v6V-U=v2,v4,v5 取邊(v6,v4),則：U=v1,v3, v6,v4V-U=v2,v5

5、 取邊(v3,v2),則：U=v1,v3, v6,v4,v2V-U=v5 取邊(v2,v5),則：U=v1,v3, v6,v4,v2,v5V-U= 82.實例：V=v1,v2,v3,v4,v5,v6 一、最小生成樹v1v2v3v4v5v66551256463任取uk=v1, 則：U=v1,V-U=v2,v3,v4,v5,v6 取邊(v1,v3),則：U=v1,v3V-U=v2,v4,v5,v6 取邊(v3,v6),則：U=v1,v3, v6V-U=v2,v4,v5 取邊(v6,v4),則：U=v1,v3, v6,v4V-U=v2,v5 取邊(v3,v2),則：U=v1,v3, v6,v4,v2

6、V-U=v5 取邊(v2,v5),則：U=v1,v3, v6,v4,v2,v5V-U= 93.算法的實現(xiàn)：一、最小生成樹v1v2v3v4v5v66551256463 用一個輔助的一維數(shù)組closedge0.n-1存儲n個頂點到U的距離： 即對于每一個viV-U, 1in , 1)用closedgei-1.lowcost存儲vi到U的最短距離(若vi已屬于U中的元素,則vi到U的距離為0)； 2)用closedgei-1.adjvex存儲vi到U的最短距離所鄰接的那個頂點的值。用順序存儲結構(Mgraph G)存儲圖，即利用一個二維數(shù)組(G.arcs)存儲圖的鄰接矩陣，用一個一維數(shù)組(G.vex

7、s)存儲各頂點的值。10一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)：01234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 11一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1

8、2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)：01234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 12一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v16v11v15v1v1v1v2,v3,v4,v5,v6201234

9、501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 打印(v1,v3), 也即打?。?closedgek.adjvex，G.vexsk)13一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v16v10v15v1v1v1v2, v3,v4,v5,v6201234501G

10、.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 用二維數(shù)組的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexsK 的值(即v3)取代相應的adjvex的值。14一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v35v10v

11、15v36v34v1v2, v4,v5,v6201234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 15一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)：01234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 16一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5

12、 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v35v10v15v36v34v1,v3v2, v4,v5,v6501234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 打印(v3,v6), 也即打?。?closedge5.adjvex，G.vexs5)17一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3

13、 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v35v10v15v36v30v1,v3v2, v4,v5,v6501234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 用二維數(shù)組的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexsK 的值(即v6)取代相應的adjvex的值。18一、最小生成樹v1v2v3v4v

14、5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v35v10v62v36v30v1,v3,v6v2, v4,v5501234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 19一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6

15、4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)：01234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 20一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlow

16、costv10v35v10v62v36v30v1,v3,v6v2, v4,v5301234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 打印(v6,v4), 也即打?。?closedge3.adjvex，G.vexs3)21一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowco

17、stv10v35v10v60v36v30v1,v3,v6v2, v4,v5301234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 用二維數(shù)組的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexsK 的值(即v4)取代相應的adjvex的值。22一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的

18、實現(xiàn)：01234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 23一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v35v10v60v36v30v1,v3,v6,v4v2,v5101234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 打印

19、(v3,v2), 也即打?。?closedge1.adjvex，G.vexs1)24一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v30v10v60v36v30v1,v3,v6,v4v2,v5101234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 用二維數(shù)組

20、的第K行與這里的lowcost行中的元素依次比較，若發(fā)現(xiàn)距離變小了，則用小值替代大值，且用G.vexsK 的值(即v2)取代相應的adjvex的值。25一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)：01234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 26一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分

21、析 6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)： iclosedge012345UV-UKadjvexlowcostv10v30v10v60v23v30v1,v3,v6,v4,v2v5401234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 打印(v2,v5), 也即打?。?closedge4.adjvex，G.vexs4)27一、最小生成樹v1v2v3v4v5v66551256463 數(shù)據(jù)結構的動態(tài)分析 6

22、 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6 G.arcs如下：012345 0 1 2 3 4 5 算法執(zhí)行期間一維數(shù)組closedge的動態(tài)變化過程：3.算法的實現(xiàn)：01234501G.vexs:v1v2v3v4v5v6 0 1 2 3 4 5 28一、最小生成樹3.算法的實現(xiàn)： 算法程序29 算法程序1.復習圖的數(shù)組表示法 (MGgraph) 的定義 #define INFINITY 10000 / INFINITY用以表示#define MAX_VERTEX_NUM 20 /最大頂點數(shù)enum GraphKind DG,DN,UDG,UDN ; /枚

23、舉：有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct ArcCell VRType adj; / VRType的類型視具體情況而定。對于帶權圖，adj用以存 /放邊或弧上的權值;對于無權圖，adj用以存放0或1(int類型) /InfoType * info; /一般情況下可以不使用該項 ArcCell , AdjMatrix MAX_VERTEX_NUM , MAX_VERTEX_NUM ; /AdiMatrix是一個類型為ArcCell的二維數(shù)組,用以存放弧或邊的鄰接關系或權值typedef struct VertexType vexs MAX_VERTEX_NUM ; / Ve

24、rtexType是頂點值的類型 /一維數(shù)組vexs用以存放各頂點的值 AdjMatrix arcs; /二維數(shù)組arcs存放邊或弧上的信息（如權值） int vexnum , arcnum; /這兩項分別存放圖的頂點數(shù)目和弧的條數(shù) GraphKind kind; / kind用以存放圖的種類標志 MGraph30 算法程序typedef struct Adjvexlowcost VertexType adjvex ; int lowcost; Adjvexlowcost , ALListMAX_VERTEX_NUM;ALList closedge; /定義一個一維數(shù)組，其每個數(shù)組下標變量 /c

25、losedgei均有兩個分量： adjvex 和lowcost / closedgei. lowcost記錄了vi到U的最短距離 / closedgei. adjvex記錄了vi到U的這個最短距依賴U中哪個頂點2.求圖的最小生成樹的輔助一維數(shù)組 closedge的定義 31 算法程序void MiniSpanTree_PRIM(MGraph G , VertexType u) k=locateVex(G,u); /在G.vexs0.G.vexnum-1中查找u,將u的序號作為返回值 closedgek.adjvex=u; closedgek.lowcost=0; /將u并入到U中 for (j

26、=0;jG.vexnum;+j) /將鄰接矩陣的第k行(如選u=v1,則k=0)作為數(shù)組 /closedge的初值 if (!j=k) closedgej.adjvex=u; closedgej.lowcost=G.arcskj.adj; for (i=1;iG.vexnum;+i)/在無向網(wǎng)中找出n-1條邊構成最小生成樹 k=minimum(closedge); /在數(shù)組closedge中查找一個k使得 /closedgek.lowcost是最小的且不等于0 printf(closedgek. adjvex, G.vexk); /輸出找到的一條最小代價邊 closedgek.lowcost=

27、0; /將vk+1添加到U中 for (j=0;jG.vexnum;+j) /用鄰接矩陣的第k行及vk+1修改closedge if (G.arcskj.adj)closedgej.lowcost) closedgej.adjvex=G.vexsk; closedgej. lowcost=G.arcskj.adj; 32void MiniSpanTree_PRIM(MGraph G , VertexType u) k=locateVex(G,u); /在G.vexs0.G.vexnum-1中查找u,將u的序號作為返回值 closedgek.adjvex=u; closedgek.lowcost

28、=0; /將u并入到U中 for (j=0;jG.vexnum;+j) /將鄰接矩陣的第k行(如選u=v1,則k=0)作為數(shù)組 /closedge的初值 if (!j=k) closedgej.adjvex=u; closedgej.lowcost=G.arcskj.adj; for (i=1;iG.vexnum;+i)/在無向網(wǎng)中找出n-1條邊構成最小生成樹 k=minimum(closedge); /在數(shù)組closedge中查找一個k使得 /closedgek.lowcost是最小的且不等于0 printf(closedgek. Adjvex, G.vexk); /輸出找到的一條最小代價邊 closedgek.lowcost=0; /將vk+1添加到U中 for (j=0;jG.vexnum;+j) /用鄰接矩陣的第k行及vk+1修