數(shù)據(jù)結(jié)構(gòu)與算法

—圖主講教員:段凌宇2014年5月30日

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2最小支撐樹

示例(a)(a)的MST(a)的MST北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page36.6.1Prim算法Prim算法的具體操作是：從圖中任意一個(gè)頂點(diǎn)開始，首先把這個(gè)頂點(diǎn)包括在MST里；然后在那些其一個(gè)端點(diǎn)已在MST里，另一個(gè)端點(diǎn)還未在MST里的邊中，找權(quán)最小的一條邊，并把這條邊包括進(jìn)MST里(和其不在MST里的那個(gè)端點(diǎn))；如此進(jìn)行下去，每次往MST里加一個(gè)頂點(diǎn)和一條權(quán)最小的邊，直到把所有的頂點(diǎn)都包括進(jìn)MST里。RobertClayPrim（1921-）at

Bell

Labs北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page4證明用Prim算法構(gòu)造的

生成樹確實(shí)是MST首先證明這樣一個(gè)結(jié)論：設(shè)T(V*，E*)是連通無向圖G=(V，E)的一棵正在構(gòu)造的生成樹，又E中有邊e=(Vx，Vy)，其中Vx∈V*，Vy不屬于V*，且e的權(quán)W(e)是所有一個(gè)端點(diǎn)在V*里，另一端不在V*里的邊的權(quán)中最小者，則一定存在G的一棵包括T(V*，E*)

的MST包括邊e=(Vx，Vy)。用反證法北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page5設(shè)G的任何一棵包括T的MST都不包括e=(Vx，Vy)，

且設(shè)T’是一棵這樣的MST。由于T’是連通的，因此有從Vx到Vy的路徑Vx，…，Vy

把邊e=(Vx，Vy)加進(jìn)樹T’，得到一個(gè)回路Vx，…，Vy，Vx×北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6上述路徑Vx，…，Vy中必有邊e’=(Vp，Vq)，其中Vp∈V*，Vq不屬于V*，由條件知W(e’)≥W(e)，從回路中去掉邊e’，回路打開，成為另一棵生成樹T”，T”包括邊

e=(Vx，Vy)，且各邊權(quán)的總和不大于T’各邊權(quán)的總和。因此，T’是一棵包括邊e的MST，與假設(shè)矛盾，即證明了我們的結(jié)論。也證明了Prim算法構(gòu)造MST的方法是正確的，因?yàn)槲覀兪菑腡包括任意一個(gè)頂點(diǎn)和0條邊開始，每一步加進(jìn)去的都是MST中應(yīng)包括的邊，直至最后得到MST?！帘本┐髮W(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page7Prim算法

的程序?qū)崿F(xiàn)voidPrim(Graph&G,ints,Edge*&MST

){

intMSTtag=0;//最小支撐樹邊的標(biāo)號(hào)

Edge*MST=newEdge[G.VerticesNum()-1];

//最小值堆

MinHeap<Edge>H(G.EdgesNum());//初始化Mark數(shù)組、距離數(shù)組

for(inti=0;i<G.VerticesNum();i++) G.Mark[i]=UNVISITED;intv=s;G.Mark[v]=VISITED;//開始頂點(diǎn)首先被標(biāo)記do{//將以v為頂點(diǎn)，另一頂點(diǎn)未被標(biāo)記的邊插入最小值堆Hfor(Edgee=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e)) if(G.Mark[G.ToVertex(e)]==UNVISITED) H.Insert(e);

//尋找下一條權(quán)最小的邊

boolFound=false; while(!H.empty()){e=H.RemoveMin();if(G.Mark[G.ToVertex(e)]==UNVISITED){Found=true;break;}}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page8北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page9if(!Found){ Print("不存在最小支撐樹。");delete[]MST;//釋放空間

MST=NULL;//MST是空數(shù)組

return; };v=G.ToVertex(e);

//在頂點(diǎn)v的標(biāo)志位上做已訪問的標(biāo)記

G.Mark[v]=VISITED;//將邊e加到MST中

AddEdgetoMST(e,MST,MSTtag++);}while(MSTtag<(G.VerticesNum()-1)); }北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page106.6.1討論P(yáng)rim算法與Dijkstra算法十分相似；唯一區(qū)別是：Prim算法要尋找的是離已加入頂點(diǎn)距離最近的頂點(diǎn)，而不是尋找離固定頂點(diǎn)距離最近的頂點(diǎn)；其時(shí)間復(fù)雜度分析與Dijkstra算法相同，即Θ(|V|2)，其中|V|為圖的頂點(diǎn)數(shù)

。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page116.6.2Kruskal算法基本思想：對于圖G=（V，E），開始時(shí)，將頂點(diǎn)集分為|V|個(gè)等價(jià)類，每個(gè)等價(jià)類只包括一個(gè)頂點(diǎn)；然后以權(quán)的大小為順序處理各條邊；

若某條邊連接兩個(gè)不同等價(jià)類的頂點(diǎn)，則這條邊被添加到MST，并將這兩個(gè)等價(jià)類被合并為一個(gè)；反復(fù)執(zhí)行此過程，直到只剩下一個(gè)等價(jià)類。JosephBernardKruskal

1928

-

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page12Kruskal算法示例北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page13北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page14Kruskal算法的

程序?qū)崿F(xiàn)voidKruskal(Graph&G,Edge*&MST

){ PartreeA(G.VerticesNum());//等價(jià)類

//最小值堆（minheap）

MinHeap<Edge>H(G.EdgesNum());

//最小支撐樹

MST=newEdge[G.VerticesNum()-1];

//最小支撐樹邊的標(biāo)號(hào)

intMSTtag=0;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15//將圖的所有邊插入最小值堆H中for(inti=0;i<G.VerticesNum();i++)

{ for(Edgee=G.FirstEdge(i);

G.IsEdge(e);e=G.NextEdge(e))

if(G.FromVertex(e)<G.ToVertex(e)) H.Insert(e); }北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16 intEquNum=G.VerticesNum();//開始時(shí)有|V|個(gè)等價(jià)類

while(EquNum>1)

{//合并等價(jià)類 Edgee=H.RemoveMin();//獲得下一條權(quán)最小邊

if(e.weight==INFINITY) {

Print("不存在最小支撐樹.”);delete[]MST;//釋放空間

MST=NULL;//MST是空數(shù)組

return; }北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17intfrom=G.FromVertex(e);intto=G.ToVertex(e);//記錄該條邊的信息

if(A.differ(from,to))//如果邊e的兩個(gè)頂點(diǎn)不在一個(gè)等價(jià)類

{//將邊e兩個(gè)頂點(diǎn)所在的兩個(gè)等價(jià)類合并為一個(gè) A.UNION(from,to);

//