最小生成樹算法詳解-文檔資料

1、1最小生成樹算法-prim& Kruskal2生成樹的概念q生成樹一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。生成樹不唯一V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5生成樹3最小代價生成樹q生成樹的代價等于其邊上的權(quán)值之和。生成樹的代價等于其邊上的權(quán)值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V5125344最小代價生成樹F兩種常用的構(gòu)造最小生成樹的方法：普里姆算法（prim）克魯斯卡爾算法（ Kruskal Kruskal）

2、5普里姆(Prim)算法q假設(shè)假設(shè)N=(VN=(V，E)E)是連通網(wǎng)，是連通網(wǎng)，TETE是是N N上最小生成樹中邊的集合。上最小生成樹中邊的集合。q算法從算法從U=uU=u0 0(u(u0 0V)V)，TE=TE=開始，重復(fù)執(zhí)行下述操作：開始，重復(fù)執(zhí)行下述操作：F在所有在所有uUuU，vV-UvV-U的邊的邊(u(u，v)v)中找一條代價最小的邊中找一條代價最小的邊(u(u0 0 ,v,v0 0),),將將其并入集合其并入集合TETE，同時將，同時將v v0 0并入并入U U集合。集合。F當(dāng)當(dāng)U=VU=V則結(jié)束，此時則結(jié)束，此時TETE中必有中必有n-1n-1條邊，則條邊，則T=(VT=(V，

3、TE)TE)為為N N的最小生的最小生成樹。成樹。q普里姆算法構(gòu)造最小生成樹的過程是從一個頂點(diǎn)普里姆算法構(gòu)造最小生成樹的過程是從一個頂點(diǎn)U=uU=u0 0 作初作初態(tài)，不斷尋找與態(tài)，不斷尋找與U U中頂點(diǎn)相鄰且代價最小的邊的另一個頂點(diǎn)，中頂點(diǎn)相鄰且代價最小的邊的另一個頂點(diǎn)，擴(kuò)充到擴(kuò)充到U U集合直至集合直至U=VU=V為止。為止。6V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-UV1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V1 ,V3 ,V6 V2 ,V4 , V5 (2)V1 ,V3 ,V6

4、 ,V4 V2, V5 (3)V1 ,V3 ,V6 ,V4 ,V2 V5 (4)V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)最小代價生成樹q普里姆算法求最小生成樹：從生成樹中只有一個頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止7V4V1V3V2V6V5165V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)UV-Uq普里姆算法求最小生成樹：從生成樹中只有一個頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹8V4V1V3V2V6V565V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 ,

5、 V5 ,V6 (1)V6V1 ,V3 ,V6 V2 ,V4 , V5 (2)46554UV-Uq普里姆算法求最小生成樹：從生成樹中只有一個頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹9V4V1V3V2V6V565V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V6V1 ,V3 ,V6 V2 ,V4 , V5 (2)4655V1 ,V3 ,V6 ,V4 V2, V5 (3)262UV-Uq普里姆算法求最小生成樹：從生成樹中只有一個頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹10V4V1V3V2V6V56V4V1V

6、31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V1 ,V3 ,V6 V2 ,V4 , V5 (2)465V1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5UV-Uq普里姆算法求最小生成樹：從生成樹中只有一個頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹11V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4

7、6V1 ,V3 ,V6 ,V4 V2, V5 (3)62V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)33UV-Uq普里姆算法求最小生成樹：從生成樹中只有一個頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價生成樹12q普里姆算法求最小生成樹：從生成樹中只有一個頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止V4V1V3V2V6V5V4V1V31V1 V2 ,V3 ,V4 , V5 ,V6 步驟(0)V1 ,V3 V2 ,V4 , V5 ,V6 (1)V2V6V5V1 ,V3 ,V6 V2 ,V4 , V5 (2)4V1 ,V3 ,V6 ,V4 V2, V5

8、 (3)2V1 ,V3 ,V6 ,V4 ,V2 V5 (4)5V1 ,V3 ,V6 ,V4 ,V2 ,V5 (5)3UV-U最小代價生成樹13普里姆(Prim)算法生成樹中只放置一個頂點(diǎn)在關(guān)聯(lián)生成樹頂點(diǎn)的邊中（即邊的一個頂點(diǎn)在生成樹中，另一個頂點(diǎn)不在）取權(quán)值最小者將選中的邊加入生成樹，同時將該邊的關(guān)聯(lián)頂點(diǎn)加入生成樹中生成樹中頂點(diǎn)數(shù)小于n?是否結(jié)束開始14l從鍵盤（或數(shù)據(jù)文件）輸入圖的信息，用普里姆算法求解從鍵盤（或數(shù)據(jù)文件）輸入圖的信息，用普里姆算法求解給定無向連通圖的最小生成樹，最后輸出最小生成樹中的給定無向連通圖的最小生成樹，最后輸出最小生成樹中的權(quán)值和所有的邊，圖的存儲結(jié)構(gòu)自行設(shè)定。權(quán)值

9、和所有的邊，圖的存儲結(jié)構(gòu)自行設(shè)定?；疽蠡疽驠例如 下圖的輸出為weight：15(v1, v3) (v3, v6) (v6, v4) (v3, v2) (v2, v5)或者(1, 3) (3, 6) (6, 4) (3, 2) (2, 5)15普里姆算法的實(shí)現(xiàn)q頂點(diǎn)集合如何表示？頂點(diǎn)集合如何表示？q最小邊如何選擇？最小邊如何選擇？q一個頂點(diǎn)加入一個頂點(diǎn)加入U U集合（生成樹中）集合（生成樹中） 如何表示？如何表示？struct int adjvex; double lowcost;closedgeMAX_VERTEX_NUM;closedgei.adjvex=kclosedgei.lo

10、wcost頂點(diǎn)i與頂點(diǎn)k鄰接頂點(diǎn)k已經(jīng)在U集合中頂點(diǎn)i加入U集合時= 016adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeclosedge2.adjvex=1 .lowcost=6closedge3.adjvex=1 .lowcost=1closedge4.adjvex=1 .lowcost=5V4V1V3V2V6V5165F當(dāng)當(dāng)U U集合中加入一個新頂點(diǎn)時，集合中加入一個新頂點(diǎn)時，V-UV-U集合中的頂點(diǎn)到集合中的頂點(diǎn)到U U的最小代價邊可能會更新的最小代價邊可能會更新V4V1V3V2V6V56512665

11、534U集合的成員：V-U集合的成員：closedge5.adjvex=1 .lowcost=closedge6.adjvex=1 .lowcost=17adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeV4V1V3V2V6V55564U集合的成員：V-U集合的成員：F當(dāng)當(dāng)U U集合中加入一個新頂點(diǎn)時，集合中加入一個新頂點(diǎn)時，V-UV-U集合中的頂點(diǎn)到集合中的頂點(diǎn)到U U的最小代價邊可能會更新的最小代價邊可能會更新V4V1V3V

12、2V6V56512665534closedge2.adjvex=3 .lowcost=5closedge4.adjvex=1 .lowcost=5closedge5.adjvex=3 .lowcost=6closedge6.adjvex=3 .lowcost=418adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeV4V1V3V2V6V5562V

13、4V1V3V2V6V56512665534F當(dāng)U集合中加入一個新頂點(diǎn)時，V-U集合中的頂點(diǎn)到U的最小代價邊可能會更新U集合的成員：V-U集合的成員：closedge2.adjvex=3 .lowcost=5closedge4.adjvex=6 .lowcost=2closedge5.adjvex=3 .lowcost=619adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcost

14、v3500v360v1,v3,v6,v4v2,v5 v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedge2V4V1V3V2V6V556F當(dāng)U集合中加入一個新頂點(diǎn)時，V-U集合中的頂點(diǎn)到U的最小代價邊可能會更新U集合的成員：V-U集合的成員：V4V1V3V2V6V56512665534closedge2.adjvex=3 .lowcost=5closedge5.adjvex=3 .lowcost=620adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v66adjvexlowcostv3

15、50v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 2adjvexlowcost000v230v1,v3,v6,v4,v2v5 v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedge5V4V1V3V2V6V53F當(dāng)U集合中加入一個新頂點(diǎn)時，V-U集合中的頂點(diǎn)到U的最小代價邊可能會更新V4V1V3V2V6V56512665534U集合的成員：V-U集合的成員：21adjvexlowcostv16v11v15v1v2,v3,v4,v5,v63adjvexlowcostv350v15v36v34v1,v3v2,v4,v5

16、,v66adjvexlowcostv350v62v360v1,v3,v6v2,v4,v5 4adjvexlowcostv3500v360v1,v3,v6,v4v2,v5 2v2v3v4v5v6UV-Uk 頂點(diǎn)iclosedgeV4V1V3V2V6V5adjvexlowcost00000v1,v3,v6,v4,v2,v5adjvexlowcost000v230v1,v3,v6,v4,v2v5 514253U集合的成員：V-U集合的成員：V4V1V3V2V6V5651266553422 圖采用鄰接矩陣表示普里姆算法求最小生成樹普里姆算法求最小生成樹 6 1 5 6 5 3 1 5 5 6 4 5

17、5 2 3 6 6 4 2 6 1234561 2 3 4 5 6graph. arac = 23 #include #include #include #define INIT 63355 #define NUM 20 using namespace std; typedef int Elemtype; typedef struct Tnode Elemtype vexNUM; int aracNUMNUM; int v,e; graph; void Init_Graph(graph &g) for(int i = 1;i=g.v;i+) for(int j = 1;j=g.v;j+

18、) g.aracij = INIT; void Create_Graph(graph &g) cout輸入頂點(diǎn),邊數(shù)目:g.vg.e; Init_Graph(g); cout輸入頂點(diǎn)信息:endl; for(int i = 1;ig.vexi; cout輸入頂點(diǎn)間下標(biāo)和權(quán)值:endl; int k,t,w; for(int i = 1;iktw; g.arackt = w; g.aractk = g.arackt; 24 void Prim(graph &g) int min_cost = 0; int lowcostNUM; /當(dāng)前最短距離 int closestNUM; /

19、頂點(diǎn)的相鄰頂點(diǎn)(closesti則為i的鄰接點(diǎn)) int sNUM; /標(biāo)志訪問節(jié)點(diǎn) for(int i = 1;i=g.v;i+) closesti = 1; /初始置各頂點(diǎn)得鄰接點(diǎn)為1 lowcosti = g.arac1i; /初始置各頂點(diǎn)的最短距離為1到頂點(diǎn)的距離 si = 0; for(int i = 1;ig.v;i+) int min = INIT; /min初始化無窮大 int j = 1; for(int k = 2;k=g.v;k+) if(lowcostkmin&!sk) /找出與源點(diǎn)相連,且權(quán)值最小的頂點(diǎn) min = lowcostk; j = k; min_c

20、ost+=min; coutclosestjjendl; /輸出符合最小生成樹的頂點(diǎn) sj = 1; /已訪問頂點(diǎn)置1 for(int t = 2;t=g.v;t+) if(g.aracjtlowcostt&!st) /從新添加的頂點(diǎn)j出發(fā),將與j相鄰的頂點(diǎn)間的權(quán)值 /與上一頂點(diǎn)的相鄰頂點(diǎn)間的權(quán)值進(jìn)行比較。選出最小權(quán)值和相應(yīng)頂點(diǎn). lowcostt = g.aracjt; closestt = j; cout最小生成樹得最短路徑為:min_costendl; 25KruskalKruskal最小生成樹KruskalKruskal算法步驟：算法步驟：5642311653465265a.帶權(quán)圖此算法可以稱為“加邊法”，初始最小生成樹邊數(shù)為0，每迭代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合里。1. 把圖中的所有邊按代價（權(quán)值）從小到大排序；2.將圖中的所有邊都去掉。 3.將邊按權(quán)值從小到大的順序添加到圖中，保證添加的過程中不會形成環(huán) （用并查集檢測 ）4. 重復(fù)(3),直到所有頂點(diǎn)都在一顆樹內(nèi)或者有n-1條邊為止。261KruskalKrus