第十三章 最小生成樹

第十三章最小生成樹第一頁，共三十一頁，編輯于2023年，星期五第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性第二頁，共三十一頁，編輯于2023年，星期五生成樹生成樹是無向連通圖的極小連通子圖。包含圖的所有n個結(jié)點，但只含圖的n-1條邊。在生成樹中添加一條邊之后，必定會形成回路或環(huán)。ABCDEHMABCDEHM無向圖G無向圖G的生成樹第三頁，共三十一頁，編輯于2023年，星期五最小生成樹

(Minimumspanningtree,MST)定義：加權(quán)無向圖的所有生成樹中邊的權(quán)值（代價）之和最小的樹。124356616555634212435615342最小代價生成樹第四頁，共三十一頁，編輯于2023年，星期五Application:Networkdesign第五頁，共三十一頁，編輯于2023年，星期五ApplicationsMSTisfundamentalproblemwithdiverseapplications.Dithering.Clusteranalysis.Maxbottleneckpaths.Real-timefaceverification.LDPCcodesforerrorcorrection.ImageregistrationwithRenyientropy.Findroadnetworksinsatelliteandaerialimagery.Reducingdatastorageinsequencingaminoacidsinaprotein.Modellocalityofparticleinteractionsinturbulentfluidflows.AutoconfigprotocolforEthernetbridgingtoavoidcyclesinanetwork.ApproximationalgorithmsforNP-hardproblems(e.g.,TSP,Steinertree).Networkdesign(communication,electrical,hydraulic,computer,road)./~eppstein/gina/mst.html第六頁，共三十一頁，編輯于2023年，星期五第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性第七頁，共三十一頁，編輯于2023年，星期五Kruscal算法基本思想：考慮圖中權(quán)值最小的邊。如果加入這條邊不會導致回路，則加入；否則考慮下一條邊，直到包含了所有的頂點實現(xiàn)：初始時，設置生成樹為（V，Φ），如果V有n個頂點，則初始的生成樹為具有n個連通分量的樹。按權(quán)值的大小逐個考慮所有的邊，如果該邊的加入能連接兩個連通分量，則加入。當生成樹只有一個連通分量時，算法結(jié)束。第八頁，共三十一頁，編輯于2023年，星期五12435661655563421、初始連通分量：{1},{2},{3},{4},{5},{6}2、反復執(zhí)行添加、放棄動作。邊 動作 連通分量

(1,3)添加 {1,3},{4},{5},{6},{2}(4,6)添加 {1,3},{4,6},{2},{5}(2,5)添加 {1,3},{4,6},{2,5}(3,6)添加 {1,3,4,6},{2,5}(1,4)放棄 因構(gòu)成回路

(3,4)放棄 因構(gòu)成回路

(2,3)添加 {1,3,4,5,6,2}最小代價生成樹12435615342第九頁，共三十一頁，編輯于2023年，星期五算法難點及解決方案如何從所有邊中選擇代價最小的邊：用一個優(yōu)先級隊列來實現(xiàn)。將所有的邊放入一個優(yōu)先級隊列，邊的優(yōu)先級就是它的權(quán)值。權(quán)值越小，優(yōu)先級越高。如何判斷加入一條邊后會不會形成回路：用并查集來實現(xiàn)。將一個連通分量表示為并查集中的一個子集，檢查一條邊加入后會不會形成回路可以通過對邊的兩個端點分別執(zhí)行Find操作。如果兩個Find的結(jié)果相同，則表示兩個端點已連通，加入這條邊會形成回路，否則將這條邊加入生成樹。添加邊的操作就是一個Union操作，將兩個端點所屬的子集歸并起來，表示其中的所有頂點都已連通。第十頁，共三十一頁，編輯于2023年，星期五定義優(yōu)先級隊列中的元素類型structedge{ intbeg,end;//邊的起點、終點和權(quán)值 TypeOfEdgew; booloperator<(constedge&rp)const {returnw<rp.w;}//重載小于運算符};第十一頁，共三十一頁，編輯于2023年，星期五kruskal算法的實現(xiàn)template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::kruskal()const{intedgesAccepted=0，u,v;edgeNode*p;edgee;DisjointSetds(Vers);//定義一個并查集priorityQueue<edge>pq;

//定義一個關于邊的優(yōu)先級隊列

//將所有的邊放入優(yōu)先級隊列for(inti=0;i<Vers;++i){

for(p=verList[i].head;p!=NULL;p=p->next)if(i<p->end){//每條邊只入隊一次

e.beg=i;e.end=p->end; e.w=p->weight; pq.enQueue(e);} }第十二頁，共三十一頁，編輯于2023年，星期五

//開始歸并while(edgesAccepted<Vers-1)

//選擇邊數(shù)不滿n-1時 {e=pq.deQueue();

//取出權(quán)值最小的邊 u=ds.Find(e.beg); v=ds.Find(e.end); if(u!=v)

//邊的起點和終點在不同的連通子圖 {edgesAccepted++; ds.Union(u,v);

//加入(u,v)歸并兩個連通子圖 cout<<'('<<verList[e.beg].ver<<',' <<verList[e.end].ver<<")\t"; }}}第十三頁，共三十一頁，編輯于2023年，星期五時間復雜度生成優(yōu)先級隊列的for循環(huán)將所有的邊入隊。需要執(zhí)行|E|次入隊，建堆時間為log|E|,生成優(yōu)先級隊列所需時間是O(|E|log|E|)。在最壞的情況下，歸并的循環(huán)可能需要檢查所有的邊。對于每條邊，最多需要執(zhí)行兩次Find操作和一次Union操作。因此，歸并循環(huán)的最壞情況的時間復雜度是O(|E|log|V|)。在一個連通圖中，一般邊數(shù)總比結(jié)點數(shù)大，所以，Kruskal算法的時間復雜度是O(E|log|E|)。第十四頁，共三十一頁，編輯于2023年，星期五第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性第十五頁，共三十一頁，編輯于2023年，星期五Prim算法從頂點的角度出發(fā)。初始時，頂點集U為空，然后逐個加入頂點，直到包含所有頂點。過程：首先選擇一個頂點，加入頂點集。然后重復下列工作，直到U=V選擇連接U和V-U中代價最小的邊（u，v）把（u，v）加入生成樹的邊集，v加入到Uv1v2v6v7v3v4v52421310758461第十六頁，共三十一頁，編輯于2023年，星期五{2,4,5,6}{1,3}(1,3)(1,2,6),(1,3,1),(1,4,5)2{2,4,5}{1,3,6}(3,6)(3,2,5),(3,4,5),(3,5,6),(3,6,4)3{2,5}{1,3,4,6}(6,4)(3,2,5),(6,4,2),(6,5,6)4{5}{1,2,3,4,6}(3,2)(3,2,5),(6,5,6),5{2,3,4,5,6}{1}初始時1V-UU選擇的邊可供選擇的邊{1,2,3,4,5,6}(2,5)(2,5,3)6124356616555634213125536442第十七頁，共三十一頁，編輯于2023年，星期五template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::prim (TypeOfEdgenoEdge)const{bool*flag=newbool[Vers];

//設計一個布爾型的一維數(shù)組flag，flag[i]=ture表示結(jié)點i在U中，否則表示結(jié)點i不在U中。

//用兩個一維數(shù)組lowCost和startNode來記錄U中的結(jié)點到V-U中結(jié)點的權(quán)值最小的邊。

TypeOfEdge*lowCost=newTypeOfEdge[Vers];

//表示U中的結(jié)點到結(jié)點i的邊的最小權(quán)值。int*startNode=newint[Vers];

//表示從U中的哪一個結(jié)點出發(fā)到結(jié)點i的權(quán)值是lowCost[i]。edgeNode*p;TypeOfEdgemin;intstart,i,j;for(i=0;i<Vers;++i){

//初始化，所有結(jié)點均不在U中，將flag的元素全部置成false；將lowCost的元素全部置成無窮大 flag[i]=false; lowCost[i]=noEdge;}Prim算法的實現(xiàn)第十八頁，共三十一頁，編輯于2023年，星期五start=0;

//將0作為第一個加入U中結(jié)點for(i=1;i<Vers;++i){

//共找n-1條邊,檢查start的邊，對于start的每一條邊(start,v)，如果v不在生成樹中，并且邊的權(quán)值w小于lowCost[v]時更新 for(p=verList[start].head;p!=NULL;p=p->next) if(!flag[p->end]&&lowCost[p->end]>p->weight){

lowCost[p->end]=p->weight;

//更新距離 startNode[p->end]=start;} flag[start]=true;

//將start加入U中 min=noEdge; for(j=0;j<Vers;++j)

//尋找權(quán)值最小的邊 if(lowCost[j]<min){min=lowCost[j];start=j;}

//將j加入U cout<<'('<<verList[startNode[start]].ver<<',‘ <<verList[start].ver<<")\t"; lowCost[start]=noEdge;

//不再考慮這條邊}delete[

]flag;delete[

]startNode;delete[

]lowCost;}第十九頁，共三十一頁，編輯于2023年，星期五prim算法運行過程中startNode和lowCost數(shù)組的變化∞隨機值∞隨機值∞隨機值∞隨機值∞隨機值∞隨機值lowCoststartNode543210編號0132456165556342651FFFFFFvisited453210編號T5564T26TT3TT0002225521第二十頁，共三十一頁，編輯于2023年，星期五時間復雜度函數(shù)的主體是一個嵌套循環(huán)，外層循環(huán)執(zhí)行|V|次，內(nèi)層循環(huán)也執(zhí)行|V|次。所以，Prim算法的時間復雜度是O（|V|2）。Doesalinear-timeMSTalgorithmexist?第二十一頁，共三十一頁，編輯于2023年，星期五第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性第二十二頁，共三十一頁，編輯于2023年，星期五算法的正確性定理13.1：假設G={V,E}是一個連通圖，U是頂點集合V的一個非空子集。若(u,v)是一條代價最小的邊，且u∈U,v∈V－U，則必存在一棵包括邊(u,v)在內(nèi)的最小生成樹。第二十三頁，共三十一頁，編輯于2023年，星期五定理的證明用反證法證明。假定在圖G={V，E}中，存在一棵不包括代價最小的邊(u,v)在內(nèi)的最小生成樹，設其為T。將邊(u,v)添加到樹T，由于頂點u,v本來就是連通的，現(xiàn)在又增加了一條新的通路，所以便形成了一條包含邊(u,v)的回路。因此，必定存在另一條邊(u’，v’)，且u’∈U,v’∈V-U。為了消除上述的回路，可以將邊(u’，v’)刪除。記為T’＝T＋(u,v)－(u’，v’)。T’仍然包含V的所有的頂點，而且這些頂點之間仍然是連通的，而且代價比T小。所以新的生成樹T‘將是代價最小的樹。和原假設矛盾，原命題得證。第二十四頁，共三十一頁，編輯于2023年，星期五總結(jié)最小生成樹是加權(quán)無向連通圖的權(quán)值和最小的極小連通子圖，它有很重要的應用價值。尋找最小生成樹的兩個經(jīng)典算法：Kruskal算法和Prim算法，給出了它們在鄰接表類中的實現(xiàn)。最后證明了兩個算法的正確性。第二十五頁，共三十一頁，編輯于2023年，星期五EuclideanMSTGivenNpointsintheplane,findMSTconnectingthem,wherethedistancesbetweenpointpairsaretheirEuclideandistances.Bruteforce.Compute~N2/2distancesandrunPrim'salgorithm.Ingenuity.Exploitgeometryanddoitin~cNlogN.第二十六頁，共三十一頁，編輯于2023年，星期五Application:Modelsofnaturehttp://algo.inria.fr/broutin/gallery.html第二十七頁，共三十一頁，編輯于2023年，星期五Scientificapplication:clusteringk-clustering.Divideasetofobjectsclassifyintokcoherentgroups.Distancefunction.Numericvaluespecifying"closeness"oftwoobjects.Goal.Divideintoclusterssothatobjectsindifferentclustersarefara