第十三章 最小生成樹(shù)

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

(Minimumspanningtree,MST)定義：加權(quán)無(wú)向圖的所有生成樹(shù)中邊的權(quán)值（代價(jià)）之和最小的樹(shù)。124356616555634212435615342最小代價(jià)生成樹(shù)第四頁(yè)，共三十一頁(yè)，編輯于2023年，星期五Application:Networkdesign第五頁(yè)，共三十一頁(yè)，編輯于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第六頁(yè)，共三十一頁(yè)，編輯于2023年，星期五第13章最小生成樹(shù)生成樹(shù)與最小生成樹(shù)Kruskal算法Prim算法算法的正確性第七頁(yè)，共三十一頁(yè)，編輯于2023年，星期五Kruscal算法基本思想：考慮圖中權(quán)值最小的邊。如果加入這條邊不會(huì)導(dǎo)致回路，則加入；否則考慮下一條邊，直到包含了所有的頂點(diǎn)實(shí)現(xiàn)：初始時(shí)，設(shè)置生成樹(shù)為（V，Φ），如果V有n個(gè)頂點(diǎn)，則初始的生成樹(shù)為具有n個(gè)連通分量的樹(shù)。按權(quán)值的大小逐個(gè)考慮所有的邊，如果該邊的加入能連接兩個(gè)連通分量，則加入。當(dāng)生成樹(shù)只有一個(gè)連通分量時(shí)，算法結(jié)束。第八頁(yè)，共三十一頁(yè)，編輯于2023年，星期五12435661655563421、初始連通分量：{1},{2},{3},{4},{5},{6}2、反復(fù)執(zhí)行添加、放棄動(dòng)作。邊 動(dòng)作 連通分量

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

//定義一個(gè)關(guān)于邊的優(yōu)先級(jí)隊(duì)列

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

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

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

//開(kāi)始?xì)w并while(edgesAccepted<Vers-1)

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

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

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

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

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

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

TypeOfEdge*lowCost=newTypeOfEdge[Vers];

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

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

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

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

//共找n-1條邊,檢查start的邊，對(duì)于start的每一條邊(start,v)，如果v不在生成樹(shù)中，并且邊的權(quán)值w小于lowCost[v]時(shí)更新 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(xiǎn)中 min=noEdge; for(j=0;j<Vers;++j)

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

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

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

]flag;delete[

]startNode;delete[

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