最小生成樹算法講解

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

｝｛V2,V3,V4,V5,V6

｝步驟(0)｛V1,V3

｝｛V2,V4,V5,V6

｝(1)UV-U普里姆算法求最小生成樹：從生成樹中只有一個(gè)頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價(jià)生成樹第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普里姆算法求最小生成樹：從生成樹中只有一個(gè)頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價(jià)生成樹第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普里姆算法求最小生成樹：從生成樹中只有一個(gè)頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價(jià)生成樹第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普里姆算法求最小生成樹：從生成樹中只有一個(gè)頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價(jià)生成樹第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普里姆算法求最小生成樹：從生成樹中只有一個(gè)頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止最小代價(jià)生成樹第11頁,共32頁，2024年2月25日，星期天普里姆算法求最小生成樹：從生成樹中只有一個(gè)頂點(diǎn)開始，到頂點(diǎn)全部進(jìn)入生成樹為止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最小代價(jià)生成樹第12頁,共32頁，2024年2月25日，星期天普里姆(Prim)算法生成樹中只放置一個(gè)頂點(diǎn)在關(guān)聯(lián)生成樹頂點(diǎn)的邊中（即邊的一個(gè)頂點(diǎn)在生成樹中，另一個(gè)頂點(diǎn)不在）取權(quán)值最小者將選中的邊加入生成樹，同時(shí)將該邊的關(guān)聯(lián)頂點(diǎn)加入生成樹中生成樹中頂點(diǎn)數(shù)小于n?是否結(jié)束開始第13頁,共32頁，2024年2月25日，星期天基本要求從鍵盤（或數(shù)據(jù)文件）輸入圖的信息，用普里姆算法求解給定無向連通圖的最小生成樹，最后輸出最小生成樹中的權(quán)值和所有的邊，圖的存儲結(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)第14頁,共32頁，2024年2月25日，星期天頂點(diǎn)集合如何表示？最小邊如何選擇？一個(gè)頂點(diǎn)加入U(xiǎn)集合（生成樹中）如何表示？struct{intadjvex;doublelowcost;}closedge[MAX_VERTEX_NUM];closedge[i].adjvex=kclosedge[i].lowcost頂點(diǎn)i與頂點(diǎn)k鄰接頂點(diǎn)k已經(jīng)在U集合中頂點(diǎn)i加入U(xiǎn)集合時(shí)普里姆算法的實(shí)現(xiàn)=0第15頁,共32頁，2024年2月25日，星期天adjvexlowcostv16v11v15

{v1}{v2,v3,v4,v5,v6}3v2v3v4v5v6UV-Uk頂點(diǎn)iclosedgeclosedge[2].adjvex=1.lowcost=6closedge[3].adjvex=1.lowcost=1closedge[4].adjvex=1.lowcost=5V4V1V3V2V6V5165當(dāng)U集合中加入一個(gè)新頂點(diǎn)時(shí)，V-U集合中的頂點(diǎn)到U的最小代價(jià)邊可能會(huì)更新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頂點(diǎn)iclosedgeV4V1V3V2V6V55564U集合的成員：V-U集合的成員：當(dāng)U集合中加入一個(gè)新頂點(diǎn)時(shí)，V-U集合中的頂點(diǎn)到U的最小代價(jià)邊可能會(huì)更新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頂點(diǎn)iclosedgeV4V1V3V2V6V5562V4V1V3V2V6V56512665534當(dāng)U集合中加入一個(gè)新頂點(diǎn)時(shí)，V-U集合中的頂點(diǎn)到U的最小代價(jià)邊可能會(huì)更新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頂點(diǎn)iclosedge2V4V1V3V2V6V556當(dāng)U集合中加入一個(gè)新頂點(diǎn)時(shí)，V-U集合中的頂點(diǎn)到U的最小代價(jià)邊可能會(huì)更新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頂點(diǎn)iclosedge5V4V1V3V2V6V53當(dāng)U集合中加入一個(gè)新頂點(diǎn)時(shí)，V-U集合中的頂點(diǎn)到U的最小代價(jià)邊可能會(huì)更新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頂點(diǎn)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;//頂點(diǎn)數(shù)、邊數(shù)

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

//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造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);//求生成樹的下一個(gè)頂點(diǎn)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);//求生成樹的下一個(gè)頂點(diǎn)k

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

∈v-u}

cout<<"("<<k

<<","<<

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

//輸出生成樹的邊

closedge[k].lowcost=0;//頂點(diǎn)k并入U(xiǎn)集合

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

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