《數(shù)據(jù)結(jié)構(gòu)：思想與方法》第13章最小生成樹

1第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性2生成樹ABCDEHMABCDEHM無向圖G無向圖G的生成樹

生成樹是無向連通圖的極小連通子圖。包含圖的所有n個(gè)結(jié)點(diǎn)，但只含圖的n-1條邊。在生成樹中添加一條邊之后，必定會形成回路或環(huán)。3最小生成樹定義：加權(quán)無向圖的所有生成樹中邊的權(quán)值（代價(jià)）之和最小的樹。實(shí)例：124356616555634212435615342左圖的最小代價(jià)生成樹4第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性5Kruscal算法基本思想：考慮圖中權(quán)值最小的邊。如果加入這條邊不會導(dǎo)致回路，則加入；否則考慮下一條邊，直到包含了所有的頂點(diǎn)實(shí)現(xiàn)：初始時(shí)，設(shè)置生成樹為（V，Φ），如果V有n個(gè)頂點(diǎn)，則初始的生成樹為具有n個(gè)連通分量的樹。按權(quán)值的大小逐個(gè)考慮所有的邊，如果改變的加入能連接兩個(gè)連通分量，則加入。當(dāng)生成樹只有一個(gè)連通分量時(shí)，算法結(jié)束。612435661655563421、初始連通分量：{1},{2},{3},{4},{5},{6}2、反復(fù)執(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}最小代價(jià)生成樹124356153427算法難點(diǎn)及解決方案如何從所有邊中選擇代價(jià)最小的邊：用一個(gè)優(yōu)先級隊(duì)列來實(shí)現(xiàn)。將所有的邊放入一個(gè)優(yōu)先級隊(duì)列，邊的優(yōu)先級就是它的權(quán)值。權(quán)值越小，優(yōu)先級越高。

如何判斷加入一條邊后會不會形成回路：用并查集來實(shí)現(xiàn)。將一個(gè)連通分量表示為并查集中的一個(gè)子集，檢查一條邊加入后會不會形成回路可以通過對邊的兩個(gè)端點(diǎn)分別執(zhí)行Find操作。如果兩個(gè)Find的結(jié)果相同，則表示兩個(gè)端點(diǎn)已連通，加入這條邊會形成回路，否則將這條邊加入生成樹。添加邊的操作就是一個(gè)Union操作，將兩個(gè)端點(diǎn)所屬的子集歸并起來，表示其中的所有頂點(diǎn)都已連通。

8定義優(yōu)先級隊(duì)列中的元素類型structedge{intbeg,end;TypeOfEdgew;booloperator<(constedge&rp)const{returnw<rp.w;}};9kruskal算法的實(shí)現(xiàn)template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::kruskal()const{intedgesAccepted=0，u,v;edgeNode*p;edgee;DisjointSetds(Vers);

priorityQueue<edge>pq;//生成優(yōu)先級隊(duì)列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);} }10 //開始?xì)w并

while(edgesAccepted<Vers-1){e=pq.deQueue();

u=ds.Find(e.beg); v=ds.Find(e.end);

if(u!=v){edgesAccepted++;ds.Union(u,v); cout<<'('<<verList[e.beg].ver<<','<<verList[e.end].ver<<")\t";

}}}11時(shí)間復(fù)雜度生成優(yōu)先級隊(duì)列的for循環(huán)將所有的邊入隊(duì)。需要的時(shí)間是O（|E|log|E|）在最壞的情況下，歸并的循環(huán)可能需要檢查所有的邊。對于每條邊，最多需要執(zhí)行兩次Find操作和一次Union操作。因此，歸并循環(huán)的最壞情況的時(shí)間復(fù)雜度是O（|E|log|V|）。在一個(gè)連通圖中，一般邊數(shù)總比結(jié)點(diǎn)數(shù)大，所以，Kruskal算法的時(shí)間復(fù)雜度是O（|E|log|E|）12第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性13Prim算法從頂點(diǎn)的角度出發(fā)。初始時(shí)，頂點(diǎn)集U為空，然后逐個(gè)加入頂點(diǎn)，直到包含所有頂點(diǎn)。過程：首先選擇一個(gè)頂點(diǎn)，加入頂點(diǎn)集。然后重復(fù)下列工作，直到U=V選擇連接U和V-U中代價(jià)最小的邊（u，v）把（u，v）加入生成樹的邊集，v加入到U14可供選擇的邊選擇的邊UV-U1初始時(shí){1}{2,3,4,5,6}2(1,2,6),(1,3,1),(1,4,5)(1,3){1,3}{2,4,5,6}3(3,2,5),(3,4,5),(3,5,6),(3,6,4)(3,6){1,3,6}{2,4,5}4(3,2,5),(6,4,2),(6,5,6)(6,4){1,3,4,6}{2,5}5(3,2,5),(6,5,6),(3,2){1,2,3,4,6}{5}6(2,5,3)(2,5){1,2,3,4,5,6}124356616555634211311361415143614212436154212435615342可供選擇的邊選擇的邊UV-U1初始時(shí){1}{2,3,4,5,6}2(1,2,6),(1,3,1),(1,4,5)(1,3){1,3}{2,4,5,6}3(3,2,5),(3,4,5),(3,5,6),(3,6,4)(3,6){1,3,6}{2,4,5}4(3,2,5),(6,4,2),(6,5,6)(6,4){1,3,4,6}{2,5}5(3,2,5),(6,5,6),(3,2){1,2,3,4,6}{5}6(2,5,3)(2,5){1,2,3,4,5,6}16Prim算法的實(shí)現(xiàn)用一個(gè)布爾型的一維數(shù)組flag來保存哪些結(jié)點(diǎn)在U中，哪些結(jié)點(diǎn)不在U中的信息。用兩個(gè)一維數(shù)組lowCost和startNode來記錄U中的結(jié)點(diǎn)到V-U中結(jié)點(diǎn)的權(quán)值最小的邊。lowCost[i]表示U中的結(jié)點(diǎn)到結(jié)點(diǎn)i的邊的最小權(quán)值。startNode[i]表示從U中的哪一個(gè)結(jié)點(diǎn)出發(fā)到結(jié)點(diǎn)i的權(quán)值是lowCost[i]。17Prim算法的偽代碼Voidprim（）{初始化：將flag的元素全部置成false；將lowCost的元素全部置成無窮大。設(shè)start=0，表示第一個(gè)放入U(xiǎn)的結(jié)點(diǎn)是0號結(jié)點(diǎn)；重復(fù)n-1次下列操作：

{對于start的每一條邊（start，v）如果v不在生成樹中，并且邊的權(quán)值w小于lowCost[v]{lowCost[v]=w；startNode[v]=start；}flag[start]=true；從lowCost中尋找最小的元素，將下標(biāo)存入start}}18prim算法運(yùn)行過程中startNode和lowCost數(shù)組的變化初始時(shí)編號startNodelowCost0隨機(jī)值∞1隨機(jī)值∞2隨機(jī)值∞3隨機(jī)值∞4隨機(jī)值∞5隨機(jī)值∞1243566165556342將0加入U(xiǎn)編號startNodelowCost0隨機(jī)值∞1062013054隨機(jī)值∞5隨機(jī)值∞19將2加入U(xiǎn)編號startNodelowCost0隨機(jī)值∞125201325426524將5加入U(xiǎn)編號startNodelowCost0隨機(jī)值∞125201352456524將3加入U(xiǎn)編號startNodelowCost0隨機(jī)值∞125201352456524將1加入U(xiǎn)編號startNodelowCost0隨機(jī)值∞125201352413524將4加入U(xiǎn)編號startNodelowCost0隨機(jī)值∞12520135241352420鄰接表類中prim算法的實(shí)現(xiàn)template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::prim(TypeOfEdgenoEdge)const{bool*flag=newbool[Vers];TypeOfEdge*lowCost=newTypeOfEdge[Vers];int*startNode=newint[Vers];edgeNode*p;TypeOfEdgemin;intstart,i,j;

for(i=0;i<Vers;++i){

flag[i]=false; lowCost[i]=noEdge;}21start=0;

for(i=1;i<Vers;++i){

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; min=noEdge; for(j=0;j<Vers;++j)

if(lowCost[j]<min){min=lowCost[j];start=j;} cout<<'('<<verList[startNode[start]].ver<<',‘<<verList[start].ver<<")\t"; lowCost[start]=noEdge;}delete[]flag;delete[]startNode;delete[]lowCost;}22時(shí)間復(fù)雜度函數(shù)的主體是一個(gè)嵌套循環(huán)，外層循環(huán)執(zhí)行|V|次，內(nèi)層循環(huán)也執(zhí)行|V|次。所以，Prim算法的時(shí)間復(fù)雜度是O（|V|2）。23第13章最小生成樹生成樹與最小生成樹Kruskal算法Prim算法算法的正確性24算法的正確性定理13.1：假設(shè)G={V,E