最小生成樹PPT演示最終

討論課題：最小生成樹的求解方法與分析點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本目錄背景知識組內(nèi)成員分工介紹最小生成樹的求解方法與分析010203點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本組內(nèi)成員及分工介紹：

組長劉先喆：編寫最小生成樹求解方法、回答問題

組員陳靜：匯報(bào)演講、制作PPT

組員何安琪：制作PPT、分析算法、探索其他解決方法

組員韓佳文：撰寫報(bào)告提問問題

組員李昕翼：撰寫報(bào)告提問問題最小連接問題交通網(wǎng)絡(luò)中，常常關(guān)注能把所有站點(diǎn)連接起來的生成樹，使得該生成樹各邊權(quán)值之和為最小。例如：假設(shè)要在某地建造5個工廠，擬修筑道路連接這5處。經(jīng)勘探，其道路可按無向邊鋪設(shè)。現(xiàn)在每條邊的長度已經(jīng)測出并標(biāo)記在對應(yīng)邊上，如果我們要求鋪設(shè)的道路總長度最短，如何鋪設(shè)？背景知識最小生成樹：在連通邊賦權(quán)圖G中求一棵總權(quán)值最小的生成樹。該生成樹稱為最小生成樹或最小代價樹。構(gòu)造最小生成樹的思想構(gòu)造最小生成樹可以有多種算法。其中多數(shù)算法利用了最小生成樹的一種簡稱為MST的性質(zhì)：假設(shè)N=(V,{E})是一個連通網(wǎng)(v代表頂點(diǎn)集，E代表邊集)，U是頂點(diǎn)集V的一個非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本普里姆算法克魯斯卡爾構(gòu)造算法最小生成樹普里姆算法從連通網(wǎng)N={V,E}中的某一頂點(diǎn)U0出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(U0,v)，將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。以后每一步從一個頂點(diǎn)在U中，而另一個頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去，直到網(wǎng)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止普里姆算法利用該圖按普里姆算法構(gòu)造一棵最小生成樹V3V2V1V4V5V65515666423V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost61V15V3V1V1V1615{V1}{V2,V3,V4,V5,V6}v3V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost51V15V3V3V1505{V1,V3}{V2,V4,V5,V6}v6V36V3464V3V6V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost004625V6V465v4V62V3V3{V1,V3,V6}{V2,V4,V5}V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost0002V4V3556V36{V1,V3,V6,V4}{V2,V5}v2V2V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost00005V2{V1,V3,V6,V4,V2}{V5}v53V23V5V1V2V5V4V6V36513246556

iclosedgev2v3v4v5v6UV-Ukadjvexlowcost000003V5{V1,V3,V6,V4,V2,v5}{}普里姆核心算法//用普里姆算法從第u個頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){ inti,j,k; Closedgeclosedge; k=LocateVex(G,u); for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化 { if(j!=k) { strcpy(closedge[j].adjvex,u); closedge[j].lowcost=G.arcs[k][j].adj; } }..\..\普里姆算法\普里姆.cpp

closedge[k].lowcost=0;//初始時,U={u} printf("最小代價生成樹的各條邊為:\n"); for(i=1;i<G.vexnum;++i) {//選擇其余G.vexnum-1個頂點(diǎn) k=MiniNum(closedge,G);//求出T的下一個結(jié)點(diǎn)：第K頂點(diǎn) printf("(%s-%s)%d\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost);//輸出生成樹的邊 closedge[k].lowcost=0;//第K頂點(diǎn)并入U(xiǎn)集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j].adj<closedge[j].lowcost) { //新頂點(diǎn)并入U(xiǎn)集后重新選擇最小邊 strcpy(closedge[j].adjvex,G.vexs[k]); closedge[j].lowcost=G.arcs[k][j].adj; } }}普里姆算法分析假設(shè)網(wǎng)中有n個頂點(diǎn)，則第一個進(jìn)行初始化的循環(huán)語句的頻度為n，第二個循環(huán)語句的頻度為n-1；其中有兩個內(nèi)循環(huán)：其一是在closedge[v].lowcost中求最小值，其頻度為n-1;其二是重新選擇具有最小代價的邊，其頻度為n。由此，普里姆算法的時間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求邊稠密的網(wǎng)的最小生成樹?？唆斔箍査惴唆斔箍査惴◤牧硪煌緩角缶W(wǎng)的最小生成樹。假設(shè)連通網(wǎng)N=(V,{E}),則令最小生成樹的初始狀態(tài)為只有n個頂點(diǎn)而無邊的非連通圖T=(V,{}),圖中每個頂點(diǎn)自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。以此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。克魯斯卡爾算法利用該圖按克魯斯卡爾算法構(gòu)造一棵最小生成樹V3V2V1V4V5V65515666423各邊權(quán)值的堆排

12345678910edgecost6155356426adjvexv1,v2v1,v3v1,v4v3,v4v2,v5v2,v3v3,v5v3,v6v4,v6v5,v66156325564

12345678910edgecost1234555666adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v3v1,v4v3,v5v5,v6v1,v2利用堆排序后結(jié)果：V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v31V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v32V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v33V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v34V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2，v35V1V3V2V5V6V41636625554

123456edgecost123455adjvexv1,v3v4,v6v2,v5v3,v6v3,v4v2,v35克魯斯卡爾核心算法for(i=0;i<G.vexnum;i++)//各頂點(diǎn)集初始化 flag[i]=i; for(i=G.arcnum,count=1;count<G.vexnum;i--) { j=G.arcs[i].v1;k=G.arcs[i].v2; if(flag[j]!=flag[k])//兩個點(diǎn)屬于不同集合 { printf("(%s-%s)%d\n",G.vexs[j],G.vexs[k],G.arcs[i].value); count++; for(l=0;l<G.vexnum;l++) if(flag[l]==flag[k])//將點(diǎn)k所在集合的點(diǎn)并入j所在集合 flag[l]=flag[j]; } }

..\..\克魯斯卡爾算法\最小生成樹.cpp克魯斯卡爾算法分析該算法至多對e條邊各掃描一次，則每次選擇最小代價的邊僅需O(loge)的時間（第一次需O(e)）。又生成樹T的每個連通分量可以看成是一個等價類，則構(gòu)造T加入新的邊的過程類似于求等價類的過程，構(gòu)造T的過程僅需O(eloge)的時間，由此，克魯斯卡爾算法的時間復(fù)雜度為O(eloge)。點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本Solin算法Rosenstiehl和管梅谷算法Dijkstra算法最小生成樹的其他求解方法Solin算法

此算法的基本思路是：將求連通帶權(quán)圖的最小生成樹的過程分為若干階段，每一階段選取若干條邊。具體步驟如下：（1）將每個頂點(diǎn)視為一棵樹，圖中所有頂點(diǎn)視為一個森林；（2）為每棵樹選取一條邊，它是該樹與其他樹相連的所有邊中權(quán)值最小的