最小生成樹算法講解

關于最小生成樹算法講解生成樹的概念生成樹一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構成一棵樹的n-1條邊。生成樹不唯一V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5生成樹第2頁,共32頁，2024年2月25日，星期天最小代價生成樹生成樹的代價等于其邊上的權值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V512534第3頁,共32頁，2024年2月25日，星期天最小代價生成樹兩種常用的構造最小生成樹的方法：普里姆算法克魯斯卡爾算法第4頁,共32頁，2024年2月25日，星期天假設N=(V，E)是連通網，TE是N上最小生成樹中邊的集合。算法從U={u0}(u0∈V)，TE={}開始，重復執(zhí)行下述操作：在所有u∈U，v∈V-U的邊(u，v)中找一條代價最小的邊(u0,v0),將其并入集合TE，同時將v0并入U集合。當U=V則結束，此時TE中必有n-1條邊，則T=(V，{TE})為N的最小生成樹。普里姆算法構造最小生成樹的過程是從一個頂點U={u0}作初態(tài)，不斷尋找與U中頂點相鄰且代價最小的邊的另一個頂點，擴充到U集合直至U=V為止。普里姆(Prim)算法第5頁,共32頁，2024年2月25日，星期天V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-U｛V1

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)｛V1,V3,V6

｝｛V2,V4,V5

｝(2)｛V1,V3,V6,V4

｝｛V2,V5

｝(3)｛V1,V3,V6,V4,V2

｝｛V5

｝(4)｛V1,V3,V6,V4,V2,V5

｝｛｝(5)最小代價生成樹普里姆算法求最小生成樹：從生成樹中只有一個頂點開始，到頂點全部進入生成樹為止第6頁,共32頁，2024年2月25日，星期天V4V1V3V2V6V5165V1V31｛V1

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)UV-U普里姆算法求最小生成樹：從生成樹中只有一個頂點開始，到頂點全部進入生成樹為止最小代價生成樹第7頁,共32頁，2024年2月25日，星期天V4V1V3V2V6V565V1V31｛V1

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)V6｛V1,V3,V6

｝｛V2,V4,V5

｝(2)46554UV-U普里姆算法求最小生成樹：從生成樹中只有一個頂點開始，到頂點全部進入生成樹為止最小代價生成樹第8頁,共32頁，2024年2月25日，星期天V4V1V3V2V6V565V4V1V31｛V1

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)V6｛V1,V3,V6

｝｛V2,V4,V5

｝(2)4655｛V1,V3,V6,V4

｝｛V2,V5

｝(3)262UV-U普里姆算法求最小生成樹：從生成樹中只有一個頂點開始，到頂點全部進入生成樹為止最小代價生成樹第9頁,共32頁，2024年2月25日，星期天V4V1V3V2V6V56V4V1V31｛V1

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)V2V6｛V1,V3,V6

｝｛V2,V4,V5

｝(2)465｛V1,V3,V6,V4

｝｛V2,V5

｝(3)62｛V1,V3,V6,V4,V2

｝｛V5

｝(4)5UV-U普里姆算法求最小生成樹：從生成樹中只有一個頂點開始，到頂點全部進入生成樹為止最小代價生成樹第10頁,共32頁，2024年2月25日，星期天V4V1V3V2V6V5V4V1V31｛V1

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)V2V6V5｛V1,V3,V6

｝｛V2,V4,V5

｝(2)46｛V1,V3,V6,V4

｝｛V2,V5

｝(3)62｛V1,V3,V6,V4,V2

｝｛V5

｝(4)5｛V1,V3,V6,V4,V2,V5

｝｛｝(5)33UV-U普里姆算法求最小生成樹：從生成樹中只有一個頂點開始，到頂點全部進入生成樹為止最小代價生成樹第11頁,共32頁，2024年2月25日，星期天普里姆算法求最小生成樹：從生成樹中只有一個頂點開始，到頂點全部進入生成樹為止V4V1V3V2V6V5V4V1V31｛V1

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)V2V6V5｛V1,V3,V6

｝｛V2,V4,V5

｝(2)4｛V1,V3,V6,V4

｝｛V2,V5

｝(3)2｛V1,V3,V6,V4,V2

｝｛V5

｝(4)5｛V1,V3,V6,V4,V2,V5

｝｛｝(5)3UV-U最小代價生成樹第12頁,共32頁，2024年2月25日，星期天普里姆(Prim)算法生成樹中只放置一個頂點在關聯(lián)生成樹頂點的邊中（即邊的一個頂點在生成樹中，另一個頂點不在）取權值最小者將選中的邊加入生成樹，同時將該邊的關聯(lián)頂點加入生成樹中生成樹中頂點數(shù)小于n?是否結束開始第13頁,共32頁，2024年2月25日，星期天基本要求從鍵盤（或數(shù)據(jù)文件）輸入圖的信息，用普里姆算法求解給定無向連通圖的最小生成樹，最后輸出最小生成樹中的權值和所有的邊，圖的存儲結構自行設定。例如下圖的輸出為weight：15(v1,v3)(v3,v6)(v6,v4)(v3,v2)(v2,v5)或者(1,3)(3,6)(6,4)(3,2)(2,5)第14頁,共32頁，2024年2月25日，星期天頂點集合如何表示？最小邊如何選擇？一個頂點加入U集合（生成樹中）如何表示？struct{intadjvex;doublelowcost;}closedge[MAX_VERTEX_NUM];closedge[i].adjvex=kclosedge[i].lowcost頂點i與頂點k鄰接頂點k已經在U集合中頂點i加入U集合時普里姆算法的實現(xiàn)=0第15頁,共32頁，2024年2月25日，星期天adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3v2v3v4v5v6UV-Uk頂點iclosedgeclosedge[2].adjvex=1.lowcost=6closedge[3].adjvex=1.lowcost=1closedge[4].adjvex=1.lowcost=5V4V1V3V2V6V5165當U集合中加入一個新頂點時，V-U集合中的頂點到U的最小代價邊可能會更新V4V1V3V2V6V56512665534U集合的成員：V-U集合的成員：closedge[5].adjvex=1.lowcost=∞closedge[6].adjvex=1.lowcost=∞第16頁,共32頁，2024年2月25日，星期天adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6v2v3v4v5v6UV-Uk頂點iclosedgeV4V1V3V2V6V55564U集合的成員：V-U集合的成員：當U集合中加入一個新頂點時，V-U集合中的頂點到U的最小代價邊可能會更新V4V1V3V2V6V56512665534closedge[2].adjvex=3.lowcost=5closedge[4].adjvex=1.lowcost=5closedge[5].adjvex=3.lowcost=6closedge[6].adjvex=3.lowcost=4第17頁,共32頁，2024年2月25日，星期天adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4v2v3v4v5v6UV-Uk頂點iclosedgeV4V1V3V2V6V5562V4V1V3V2V6V56512665534當U集合中加入一個新頂點時，V-U集合中的頂點到U的最小代價邊可能會更新U集合的成員：V-U集合的成員：closedge[2].adjvex=3.lowcost=5closedge[4].adjvex=6.lowcost=2closedge[5].adjvex=3.lowcost=6第18頁,共32頁，2024年2月25日，星期天

adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}v2v3v4v5v6UV-Uk頂點iclosedge2V4V1V3V2V6V556當U集合中加入一個新頂點時，V-U集合中的頂點到U的最小代價邊可能會更新U集合的成員：V-U集合的成員：V4V1V3V2V6V56512665534closedge[2].adjvex=3.lowcost=5closedge[5].adjvex=3.lowcost=6第19頁,共32頁，2024年2月25日，星期天

adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}2adjvexlowcost000v230{v1,v3,v6,v4,v2}{v5}v2v3v4v5v6UV-Uk頂點iclosedge5V4V1V3V2V6V53當U集合中加入一個新頂點時，V-U集合中的頂點到U的最小代價邊可能會更新V4V1V3V2V6V56512665534U集合的成員：V-U集合的成員：第20頁,共32頁，2024年2月25日，星期天

adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}2v2v3v4v5v6UV-Uk頂點iclosedgeV4V1V3V2V6V5adjvexlowcost00000{v1,v3,v6,v4,v2,v5}{}

adjvexlowcost000v230{v1,v3,v6,v4,v2}{v5}514253U集合的成員：V-U集合的成員：V4V1V3V2V6V56512665534第21頁,共32頁，2024年2月25日，星期天普里姆算法求最小生成樹∞

6

1

5∞∞

6

∞5∞3∞

1

5∞

5

6

4

5

∞5∞∞

2∞

3

6∞

∞

6∞∞426

∞123456123456圖采用鄰接矩陣表示G.arcs[][]=#defineMaxVnum50typedefint

AdjMatrix[MaxVnum][MaxVnum];//doubletypedefstruct{intvexnum,arcnum;//頂點數(shù)、邊數(shù)

AdjMatrixarcs;//鄰接矩陣}Graph;GraphG;第22頁,共32頁，2024年2月25日，星期天voidMiniSpanTree_PRIM(GraphG,intu){

//用普里姆算法從頂點u出發(fā)構造G的最小生成樹

for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=u)closedge[j]={u,G.arcs[u][j]};struct{intadjvex;doublelowcost;}closedge[MAX_VERTEX_NUM];

closedge[u].lowcost=0;//初始,U={u}

for(i=1;i<G.vexnum;++i){

k=minimum(closedge);//求生成樹的下一個頂點kcout<<closedge[k].adjvex<<G.vexs[k];closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};

}//for}//MiniSpanTree_PRIM

k=minimum(closedge);//求生成樹的下一個頂點k

//此時closedge[k].lowcost=//MIN{closedge[vi].lowcost|closedge[vi].lowcost>0,vi

∈v-u}

cout<<"("<<k

<<","<<

closedge[k].adjvex<<")";

//輸出生成樹的邊

closedge[k].lowcost=0;//頂點k并入U集合

for(j=0;j<G.vexnum;++j)if(G.arcs[k][j]<closedge[j].lowcost)closedge[j].adjvex=k,closedge[j].Lowcost=G.arcs[k][j];算法的時間復雜度為：O(n2){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[u][j];}第23頁,共32頁，2024年2月25日，星期天選做內容從鍵盤輸入（或從文件讀入）圖的信息，用克魯斯卡爾算法求解給定無向連通圖的最小生成樹，最后輸出最小生成樹中的權值和所有的邊。

第24頁,共32頁，2024年2月25日，星期天克魯斯卡爾(Kruskal)算法假設連通網N=(V，E)，則令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V，{})，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，