第14講 圖的生成樹(shù)

第十四講圖的生成樹(shù)主講：朱鄭州《數(shù)據(jù)結(jié)構(gòu)》DataStructure主要內(nèi)容2.Prim算法1.圖的連通性3.Kruskal算法要想判定一個(gè)無(wú)向圖是否為連通圖，或有幾個(gè)連通分量，通過(guò)對(duì)無(wú)向圖遍歷即可得到結(jié)果。非連通圖：需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過(guò)程中得到的頂點(diǎn)訪問(wèn)序列恰為其各個(gè)連通分量中的頂點(diǎn)集。連通圖：僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索（或廣度優(yōu)先搜索），便可訪問(wèn)到圖中所有頂點(diǎn)。無(wú)向圖的連通性count=0;2.for(圖中每個(gè)頂點(diǎn)v)2.1if(v尚未被訪問(wèn)過(guò))2.1.1count++;2.1.2從v出發(fā)遍歷該圖；3.if(count==1)printf("圖是連通的“);elseprintf("圖中有count個(gè)連通分量");求無(wú)向圖的連通分量無(wú)向圖的連通性⑴從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷，并按其所有鄰接點(diǎn)都訪問(wèn)（即出棧）的順序?qū)㈨旤c(diǎn)排列起來(lái)。⑵從最后完成訪問(wèn)的頂點(diǎn)出發(fā)，沿著以該頂點(diǎn)為頭的弧作逆向的深度優(yōu)先遍歷。若不能訪問(wèn)到所有頂點(diǎn)，則從余下的頂點(diǎn)中最后訪問(wèn)的那個(gè)頂點(diǎn)出發(fā)，繼續(xù)作逆向的深度優(yōu)先遍歷，直至有向圖中所有頂點(diǎn)都被訪問(wèn)到為止。⑶每一次逆向深度優(yōu)先遍歷所訪問(wèn)到的頂點(diǎn)集便是該有向圖的一個(gè)強(qiáng)連通分量的頂點(diǎn)集。有向圖的連通性（a）深度優(yōu)先生成樹(shù)（b）廣度優(yōu)先生成樹(shù)V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8圖的生成樹(shù)由深度優(yōu)先遍歷得到的為深度優(yōu)先生成樹(shù)，由廣度優(yōu)先遍歷得到的為廣度優(yōu)先生成樹(shù)。一個(gè)連通圖的生成樹(shù)可能不唯一，由不同的遍歷次序、從不同頂點(diǎn)出發(fā)進(jìn)行遍歷都會(huì)得到不同的生成樹(shù)。對(duì)于非連通圖，通過(guò)圖的遍歷，將得到的是生成森林。結(jié)論：圖的生成樹(shù)生成樹(shù)的代價(jià)：設(shè)G=（V，E）是一個(gè)無(wú)向連通網(wǎng)，生成樹(shù)上各邊的權(quán)值之和稱為該生成樹(shù)的代價(jià)。最小生成樹(shù)(MinimumSpanningTree,MST)：在圖G所有生成樹(shù)中，代價(jià)最小的生成樹(shù)稱為最小生成樹(shù)。最小生成樹(shù)的概念可以應(yīng)用到許多實(shí)際問(wèn)題中。例：在n個(gè)城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，而每?jī)蓚€(gè)城市之間架設(shè)通信線路的造價(jià)是不一樣的，那么如何設(shè)計(jì)才能使得總造價(jià)最小？最小生成樹(shù)假設(shè)G=(V,E)是一個(gè)無(wú)向連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹(shù)。頂點(diǎn)集UV－Uu'vv'u頂點(diǎn)集T1T2最小生成樹(shù)性質(zhì)主要內(nèi)容2.Prim算法1.圖的連通性3.Kruskal算法基本思想：設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是G的最小生成樹(shù)，T的初始狀態(tài)為U={u0}（u0∈V），TE={}，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價(jià)最小的邊(u,v)并入集合TE，同時(shí)v并入U(xiǎn)，直至U=V。關(guān)鍵:是如何找到連接U和V-U的最短邊。利用MST性質(zhì)，可以用下述方法構(gòu)造候選最短邊集：對(duì)應(yīng)V-U中的每個(gè)頂點(diǎn)，保留從該頂點(diǎn)到U中的各頂點(diǎn)的最短邊。普里姆（Prim）算法U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725ABEDCF普里姆（Prim）算法251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,(F,D)25,(F,E)26}普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}

普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}

普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C,D,E}V-U={B}cost={(E,B)12}

普里姆（Prim）算法251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}普里姆（Prim）算法數(shù)組lowcost[n]：用來(lái)保存集合V-U中各頂點(diǎn)與集合U中頂點(diǎn)最短邊的權(quán)值，lowcost[v]=0表示頂點(diǎn)v已加入最小生成樹(shù)中；數(shù)組adjvex[n]：用來(lái)保存依附于該邊（集合V-U中各頂點(diǎn)與集合U中頂點(diǎn)的最短邊）在集合U中的頂點(diǎn)。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)表示頂點(diǎn)vi和頂點(diǎn)vk之間的權(quán)值為w，其中：vi∈V-U且vk

∈Ulowcost[i]=wadjvex[i]=k如何用數(shù)組lowcost和adjvex表示候選最短邊集？普里姆（Prim）算法

i

數(shù)組B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U輸出adjvexlowcostA34A46A∞A∞A19{A}{B,C,D,E,F}(AF)19adjvexlowcostA34F25F25F26

{A,F}{B,C,D,E}(FC)25adjvexlowcostA34

C17F26

{A,F,C}{B,D,E}(CD)17adjvexlowcostA34

F26

{A,F,C,D}{B,E}(FE)26adjvexlowcostE12

{A,F,C,D,E}{B}(EB)12adjvexlowcost

{A,F,C,D,E,B}{}

普里姆（Prim）算法1.初始化兩個(gè)輔助數(shù)組lowcost和adjvex；2.輸出頂點(diǎn)u0，將頂點(diǎn)u0加入集合U中；3.重復(fù)執(zhí)行下列操作n-1次

3.1在lowcost中選取最短邊，取adjvex中對(duì)應(yīng)的頂點(diǎn)序號(hào)k；

3.2輸出頂點(diǎn)k和對(duì)應(yīng)的權(quán)值；

3.3將頂點(diǎn)k加入集合U中；

3.4調(diào)整數(shù)組lowcost和adjvex；Prim算法——偽代碼

普里姆（Prim）算法主要內(nèi)容2.Prim算法1.圖的連通性3.Kruskal算法基本思想：設(shè)無(wú)向連通網(wǎng)為G＝(V,E)，令G的最小生成樹(shù)為T(mén)＝(U,TE)，其初態(tài)為U＝V，TE＝{}，然后，按照邊的權(quán)值由小到大的順序，考察G的邊集E中的各條邊。若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊作為最小生成樹(shù)的邊加入到T中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍去此邊，以免造成回路，如此下去，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，此連通分量便為G的一棵最小生成樹(shù)?？唆斔箍枺↘ruskal）算法251234192646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}克魯斯卡爾（Kruskal）算法251234192646381725ABEDCFABEDCF連通分量＝{A},{B},{C},{D},{E},{F}12連通分量＝{A},{B,E},{C},{D},{F}克魯斯卡爾（Kruskal）算法251234192646381725ABEDCFABEDCF12連通分量＝{A},{B,E},{C},{D},{F}克魯斯卡爾（Kruskal）算法17連通分量＝{A},{B,E},{C,D},{F}251234192646381725ABEDCFABEDCF連通分量＝{A},{B,E},{C,D},{F}12連通分量＝{A,F},{B,E},{C,D}19克魯斯卡爾（Kruskal）算法17251234192646381725ABEDCFABEDCF連通分量＝{A,F},{B,E},{C,D}12連通分量＝{A,F,C,D},{B,E}191725克魯斯卡爾（Kruskal）算法251234192646381725ABEDCFABEDCF連通分量＝{A,F,C,D},{B,E}12連通分量＝{A,F,C,D,B,E}19172526克魯斯卡爾（Kruskal）算法1.初始化：U=V；TE={}；2.循環(huán)直到T中的連通分量