最小生成樹PPT演示最終

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

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

組員陳靜：匯報演講、制作PPT

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

組員韓佳文：撰寫報告提問問題

組員李昕翼：撰寫報告提問問題最小連接問題交通網(wǎng)絡(luò)中，常常關(guān)注能把所有站點連接起來的生成樹，使得該生成樹各邊權(quán)值之和為最小。例如：假設(shè)要在某地建造5個工廠，擬修筑道路連接這5處。經(jīng)勘探，其道路可按無向邊鋪設(shè)?，F(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代表頂點集，E代表邊集)，U是頂點集V的一個非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。點擊添加文本點擊添加文本點擊添加文本點擊添加文本普里姆算法克魯斯卡爾構(gòu)造算法最小生成樹普里姆算法從連通網(wǎng)N={V,E}中的某一頂點U0出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(U0,v)，將其頂點加入到生成樹的頂點集合U中。以后每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去，直到網(wǎng)中的所有頂點都加入到生成樹頂點集合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個頂點出發(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個頂點 k=MiniNum(closedge,G);//求出T的下一個結(jié)點：第K頂點 printf("(%s-%s)%d\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost);//輸出生成樹的邊 closedge[k].lowcost=0;//第K頂點并入U集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j].adj<closedge[j].lowcost) { //新頂點并入U集后重新選擇最小邊 strcpy(closedge[j].adjvex,G.vexs[k]); closedge[j].lowcost=G.arcs[k][j].adj; } }}普里姆算法分析假設(shè)網(wǎng)中有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個頂點而無邊的非連通圖T=(V,{}),圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。以此類推，直至T中所有頂點都在同一連通分量上為止。克魯斯卡爾算法利用該圖按克魯斯卡爾算法構(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++)//各頂點集初始化 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])//兩個點屬于不同集合 { 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])//將點k所在集合的點并入j所在集合 flag[l]=flag[j]; } }

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

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