計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第9章 圖的最小支撐樹

1第9

章

圖的最小支撐樹什么是圖的最小支撐樹

2一個(gè)通用的貪心法策略

4Kruskal算法

11Prim算法

181.什么是圖的最小支撐樹無(wú)向圖G的一個(gè)子圖，如果包含所有頂點(diǎn)，則稱為G的一個(gè)支撐子圖無(wú)向圖G的一個(gè)支撐子圖，如果是一棵樹，則稱為圖G的一棵支撐樹。連通的無(wú)向圖才有支撐樹。加權(quán)圖G的一棵支撐樹T稱為最小支撐樹(minimumspanningtree，簡(jiǎn)稱MST)，如果它的邊的總權(quán)值，記作W(T)，是所有支撐樹中最小的。討論如何為連通的加權(quán)無(wú)向圖G找出最小支撐樹的算法問(wèn)題很多應(yīng)用問(wèn)題可建模為找MST的問(wèn)題。23例：(a)

一個(gè)連通的加權(quán)無(wú)向圖Gaecbd4751243(c)

一個(gè)非最小的支撐樹，權(quán)值=16aecbd7513(d)

一個(gè)最小支撐樹，權(quán)值=10aecbd1243(b)

一個(gè)支撐子圖aecbd475124

設(shè)連通加權(quán)圖G(V,E)中，|V|=n，|E|=m，步驟如下：第一步，初始化邊的集合A。 //含n個(gè)孤立頂點(diǎn)第二步，在E中找出一條邊e使得集合A{e}包含在某個(gè)MST中。第三步，如果當(dāng)前的A形成一個(gè)支撐樹，也就是含n-1條邊，算法停止，A

是一個(gè)MST。否則，重復(fù)第二步。Kruskal和Prim算法都遵循這一策略。顯然，主要問(wèn)題是在第二步中，如何找到這樣的邊。這條邊稱為安全邊。2.一個(gè)通用的貪心法策略5通用算法的偽碼Generic-MST(G(V,E))A

ConstructgraphT(V,A) //初始，T含n個(gè)頂點(diǎn)，沒(méi)有邊f(xié)ork1to

n-1

findasafeedge(u,v)inEforA

//從E中找一條安全邊(u,v)

A

A

{(u,v)}

//把邊(u,v)加到集合A中endfor

returnTEnd下面討論如何找安全邊。6割的定義及割的最小交叉邊圖的一個(gè)割

C

=(P,V-P)，就是把V分成兩個(gè)非空子集，每個(gè)頂點(diǎn)必須屬于P或者V-P，但不能同屬于兩者。給定一個(gè)割，C=(P,V-P)，如果邊(u,v)的兩端，u和v分屬于兩邊，即u

P

和v

V-P，那么我們說(shuō)，割C與邊(u,v)相交，邊(u,v)是一條交叉邊(Crossedge)。如果一個(gè)割，C=(P,V-P)，與集合A

E

中每一條邊都不相交，那么，我們說(shuō)這個(gè)割尊重(respect)集合A。給定一個(gè)割，C=(P,V-P)，所有交叉邊組成的集合稱為邊與這個(gè)割的交集，記為B(C)。交集B(C)中權(quán)值最小的邊稱為最小交叉邊。7割的最小交叉邊的例子下圖中，P={a,b,d,f,h},V-P={c,e,g,i}。粗線條表示A中的邊，并與割C=(P,V-P)不相交。交集B(C)={(a,c)，(b,g)，(d,c)，(d,e)，(d,g)，(h,g)，(h,i)}。最小交叉邊是(b,g)，權(quán)值為w(b,g)=2。8定理9.1

A

E是E的一個(gè)子集且包含在某個(gè)MST中。如果有一個(gè)割C=(P,V-P)與A不相交，那么它的最小交叉邊是一條安全邊。證明：

我們只需證明

A

{(u,v)}包含在某一個(gè)MST中。假設(shè)T*是一個(gè)包含A的MST，而邊(u,v)是割C

的最小交叉邊。如果邊(u,v)也屬于T*，那么定理得證?？紤](u,v)

T*的情況。因?yàn)門*是個(gè)支撐樹，有一條從u到v的路徑L。因?yàn)閡和v分屬割的兩邊，所以，如果沿著從u到v的路徑L走，一定會(huì)碰到另一條交叉邊(x,y)。下圖顯示了這種情況。圖中粗線條表示集合A里的邊。如果把(x,y)刪去，會(huì)把T*斷開為兩個(gè)子樹，分別含u和v。(接下頁(yè))9這時(shí)，如果把(u,v)加進(jìn)去，則會(huì)把這兩個(gè)子樹又連成一個(gè)支撐樹T’，T’=(T*

–{(x,y)}

{(u,v)})。因?yàn)?u,v)是最小交叉邊，w(u,v)

w(x,y)，所以有：W(T’)=W(T*)–w(x,y)+w(u,v)

W(T*)。因?yàn)門*是一個(gè)MST，T’也必定是一個(gè)MST且包含了邊(u,v)。所以，集合A

{(u,v)}包含在某一個(gè)MST中。

定理9.1 證明(繼續(xù))10定理9.1意味著最小支撐樹的通用算法是正確的。這是因?yàn)椋?. 因?yàn)閨V|=n，只要

|A|<

n-1，導(dǎo)出的圖T就不連通，集合V就必有與A不相交的割

C=(P，V-P)。因?yàn)檫B通的G必有連接割的兩邊的邊，即P和V-P之間的邊，也就是交叉邊，所以就一定可以找到安全邊。當(dāng)|A|=n-1時(shí)，圖T必定是一棵有n個(gè)點(diǎn)的樹。因?yàn)樗谀硞€(gè)MST中，那么它必定就是一個(gè)MST。

11Kruskal算法可簡(jiǎn)單表述如下：MST-Kruskal-Abstract(G(V,E)) //G是一個(gè)加權(quán)的連通圖A

//集合A初始化為空集ConstructgraphT(V,A) //初始時(shí)，T含有n個(gè)孤立頂點(diǎn)Sortedgessuchthate1

e2

…

em

//圖G的邊按權(quán)值排序

for

i

1to

m

//逐條邊檢查并做取舍選擇

if

A

{ei}hasnocycle

//把邊ei加到A中不產(chǎn)生回路

then

A

A

{ei} //那么就把ei

選上并加到A中

endif

//否則，邊ei加到A中會(huì)產(chǎn)生回路endforreturn

T(V,A)

//由頂點(diǎn)集合V和邊集合A構(gòu)成的圖就是MSTEnd3.Kruskal算法12正確性證明：歸納法證明:算法每一次對(duì)ei(1

i

m)的取舍都是正確的，而且使T(V,A)包含在一個(gè)MST中。歸納基礎(chǔ)：當(dāng)i=0時(shí)，集合A為空集，T(V,A)顯然包含在任一個(gè)MST中。歸納步驟：假設(shè)算法對(duì)前i-1條邊做了正確選擇，這時(shí)的T(V,A)包含在某個(gè)MST中。我們證明算法對(duì)邊ei

的決定也是正確的。分兩種情況。算法不選取邊ei。這說(shuō)明，把

ei加到子圖A中后產(chǎn)生回路。因?yàn)槿魏螛洳缓芈罚热磺懊孢x取的邊是正確的，那么

ei

不可取。另外，回路說(shuō)明，ei

不可能是任何尊重A的割的交叉邊，所以ei不可取。(接下頁(yè))13正確性證明(継續(xù))算法選取邊ei。這說(shuō)明，ei

A無(wú)回路。假設(shè)ei=(u,v)。在ei

之前，u和v在T(V,A)中必分屬不同連通分支?？蓸?gòu)造割C

=(P,V-P)，其中P含有所有與頂點(diǎn)u連通的點(diǎn)。顯然，C

與A不相交，C

尊重A。ei

必定是最小交叉邊，因?yàn)闄?quán)值比ei

小的邊都已檢查過(guò)，要么已被選在集合A中，要么已被丟棄。被丟棄的邊不可能是交叉邊，因?yàn)樗麄兣cA中邊形成回路，不可能與割C相交。根據(jù)定理9.1，ei=(u,v)是個(gè)安全邊。歸納成功。所以，算法結(jié)束時(shí)，T(V,A)屬于一個(gè)MST。這時(shí)，T(V,A)必定是個(gè)連通圖，否則，運(yùn)算中一定丟棄了一條連結(jié)不同分支的邊，這與算法矛盾。因?yàn)門(V,A)含n個(gè)頂點(diǎn)，它就是一個(gè)MST。14算法復(fù)雜度邊的排序需要O(mlgn)時(shí)間。如何檢測(cè)

A

{ei

}

是否有回路？Union-Find算法概述(見(jiàn)書中簡(jiǎn)介，詳見(jiàn)附錄B)A中每個(gè)連通分支中的點(diǎn)組織為一個(gè)集合，并分配一個(gè)分支號(hào)。初始，每個(gè)頂點(diǎn)u形成一個(gè)集合，用Make-Set(u)表示這個(gè)初始化操作。每檢查一條邊(u,v)時(shí)，做兩件事：找出u和v的分支號(hào)。用Find(u)和Find(v)表示找分支號(hào)的操作。如果u和v的分支號(hào)相同，邊(u,v)的加入會(huì)形成回路，不選這條邊。否則，把這條邊加到子圖A中。這時(shí)，u和v分屬的兩連通分支就合成一個(gè)分支了，需要把它們對(duì)應(yīng)的集合并為一個(gè)集合并保留一個(gè)分支號(hào)。我們用Union(u,v)表示這個(gè)操作。Union-Find

算法對(duì)m條邊的操作復(fù)雜度是O(m

(n))。

(n)是Ackermann函數(shù)的反函數(shù)，增長(zhǎng)極慢，可認(rèn)為常數(shù)。15用Union-Find后，Kruskal算法可寫得更具體些。MST-Kruskal(G(V,E)A

ConstructgraphT(V,A) //圖T有頂點(diǎn)集合V，邊的集合ASortedgessuchthate1

e2

…

em

foreachvertexv

V Make-Set(v) //初始化T中每個(gè)分支endforfor

i

1tom

Letei

=(u,v) ifFind(u)

Find(v) then

A

A

{ei} //

ei

是一條安全邊

Union(u,v) //把u和v所在子樹合并

endifendforreturngraphT(V,A)EndKruskal算法復(fù)雜度是O(mlgn+m

(n))=O(mlgn)。16例9.1

圖示Kruskal算法逐步找出下面無(wú)向圖的一個(gè)MST的過(guò)程。aecbd4751243f69解：aecbd4751243f69(a)aecbd4751243f69(b)aecbd4751243f69(c)aecbd4751243f69(d)17aecbd4751243f69(e)aecbd4751243f69(f)aecbd4751243f69(g)aecbd4751243f69(h)aecbd1243f6(j)aecbd4751243f69(i)18給定邊的集合A，定義頂點(diǎn)集合V(A)={v|

(u,v)

A}}。與Kruskal算法不同的是，集合A的邊只形成一個(gè)連通分支，即一棵正在逐步發(fā)展的樹，T(V(A)，A)，簡(jiǎn)稱為樹A。每步使用的割是把V(A)放在割的一邊，而其余頂點(diǎn)則放在割的另一邊，即C=(V(A)，V-

V(A))。為樹外的點(diǎn)v

V-V(A)，定義d(v)=min{w(u,v)|u

V(A)}如果d(v)=w(u,v)，則稱u為v的父親，記

(v)=u。

(u,v)是所有與點(diǎn)v關(guān)聯(lián)的交叉邊中權(quán)值最小的邊。

d(v)稱為點(diǎn)v到樹A的距離。(u,v)稱為v的距離邊。初始化取點(diǎn)s

為根，A

=，V(A)=

，d(s)=0，

(s)=nil。其余點(diǎn)v

V–{s}，初始為d(v)=(v

s)，

(v)=nil。3.Prim算法19

20sbc割C=(V(A),V-V(A))a頂點(diǎn)集合V(A)邊集合A集合V–V(A)yxz7846810d(x)=7

(x)=bd(y)=6

(y)=cd(z)=8

(z)=c(c,y)是安全邊，d(y)=6是所有當(dāng)前樹A之外的點(diǎn)到樹A的最短距離。當(dāng)邊(c,y)加到集合A后，d(x)要更新為d(x)=4，

(x)=y。21MST-Prim(G(V,E),s)for

eachv

V //初始化

d(v)

，

(v)

nilendford(s)

0 //使下面第一次循環(huán)產(chǎn)生只含s一個(gè)點(diǎn)的樹A

//邊的集合初始為空V(A)

//頂點(diǎn)集合V(A)初始為空Q

V

//以d(v)為關(guān)鍵字，用Q把所有點(diǎn)v組織起來(lái)while

Q

u

Extract-Min(Q) //d(u)值最小并從Q中剝離，修復(fù)Q

A

A

{(

(u),u)} //集合A多了一條邊，

(u)=nil時(shí)，不操作

V(A)

V(A){u}

//點(diǎn)的集合V(A)多了一個(gè)點(diǎn)

foreachv

Adj(u)

if

v

Q

and

w(u,v)<d(v) //如是，則更新d(v)和修復(fù)Q

then

d(v)

w(u,v)，

(v)

u

endif

endforendwhilereturnT(V(A),A) //以V(A)為頂點(diǎn)集合，以A為邊的樹End22例: 圖示Prim算法逐步求圖9-1的MSTaecbd4751243f69(b)點(diǎn)a被選，更新b，d，e，fd(a)=0

(a)=nild(b)=4

(b)=ad(c)=

(c)=nild(d)=5

(d)=ad(e)=2

(e)=ad(f)=6

(f)=aaecbd4751243f69(a)初始狀態(tài)d(a)=0

(a)=nild(b)=

(b)=nild(c)=

(c)=nild(d)=

(d)=nild(e)=

(e)=nild(f)=

(f)=nil23aecbd4751243f69(d)點(diǎn)b被選，更新cd(a)=0

(a)=nild(b)=3

(b)=ed(c)=7

(c)=bd(d)=4

(d)=ed(e)=2

(e)=ad(f)=6

(f)=aaecbd4751243f69(c)點(diǎn)e被選，更新b，dd(a)=0

(a)=nild(b)=3

(b)=ed(c)=

(c)=nild(d)=4

(d)=ed(e)=2

(e)=ad(f)=6

(f)=a24aecbd4751243f69(e)點(diǎn)d被選，更新cd(a)=0

(a)=nild(b)=3

(b)=ed(c)=1

(c)=dd(d)=4

(d)=ed(e)=2

(e)=ad(f)=6

(f)=aaecbd4751243f69(f)點(diǎn)c被選，無(wú)點(diǎn)須更新d(a)=0

(a)=nild(b)=3

(b)=ed(c)=1

(c)=dd(d)=4

(d)=ed(e)=2

(e)=ad(f)=6

(f)=aaecbd4751243f69(g)點(diǎn)f被選，無(wú)點(diǎn)須更新d(a)=0

(a)=nild(b)=3

(b)=ed(c)=1

(c)=dd(d)=4

(d)=ed(e)=2

(e)=ad(f)=6

(f)=aaecbd1243f6(h)得到的MSTd(d)=4

(d)=ed(e)=2

(e)=a25Prim算法復(fù)雜度復(fù)雜度取決于用什么數(shù)據(jù)結(jié)構(gòu)Q來(lái)存儲(chǔ)d(v)，v

V。用數(shù)組作為Q。算法主要部分是while循環(huán)，進(jìn)行n次，每次做兩件事。一是找出最小d(u)，并把邊(

(u),u)加入集合A中。二是更新點(diǎn)u