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

1第9

章

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

2一個通用的貪心法策略

4Kruskal算法

11Prim算法

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

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

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

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

一個支撐子圖aecbd475124

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

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

ConstructgraphT(V,A) //初始，T含n個頂點，沒有邊f(xié)ork1to

n-1

findasafeedge(u,v)inEforA

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

A

A

{(u,v)}

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

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

C

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

P

和v

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

E

中每一條邊都不相交，那么，我們說這個割尊重(respect)集合A。給定一個割，C=(P,V-P)，所有交叉邊組成的集合稱為邊與這個割的交集，記為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的一個子集且包含在某個MST中。如果有一個割C=(P,V-P)與A不相交，那么它的最小交叉邊是一條安全邊。證明：

我們只需證明

A

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

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

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

–{(x,y)}

{(u,v)})。因為(u,v)是最小交叉邊，w(u,v)

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

W(T*)。因為T*是一個MST，T’也必定是一個MST且包含了邊(u,v)。所以，集合A

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

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

|A|<

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

C=(P，V-P)。因為連通的G必有連接割的兩邊的邊，即P和V-P之間的邊，也就是交叉邊，所以就一定可以找到安全邊。當|A|=n-1時，圖T必定是一棵有n個點的樹。因為它包含在某個MST中，那么它必定就是一個MST。

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

//集合A初始化為空集ConstructgraphT(V,A) //初始時，T含有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中會產(chǎn)生回路endforreturn

T(V,A)

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

i

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

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

ei加到子圖A中后產(chǎn)生回路。因為任何樹不含回路，既然前面選取的邊是正確的，那么

ei

不可取。另外，回路說明，ei

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

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

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

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

與A不相交，C

尊重A。ei

必定是最小交叉邊，因為權(quán)值比ei

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

A

{ei

}

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

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

(n))。

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

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

e2

…

em

foreachvertexv

V Make-Set(v) //初始化T中每個分支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算法逐步找出下面無向圖的一個MST的過程。aecbd4751243f69解：aecbd4751243f69(a)aecbd4751243f69(b)aecbd4751243f69(c)aecbd4751243f69(d)17aecbd4751243f69(e)aecbd4751243f69(f)aecbd4751243f69(g)aecbd4751243f69(h)aecbd1243f6(j)aecbd4751243f69(i)18給定邊的集合A，定義頂點集合V(A)={v|

(u,v)

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

V(A))。為樹外的點v

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

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

(v)=u。

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

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

為根，A

=，V(A)=

，d(s)=0，

(s)=nil。其余點v

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

s)，

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

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

(x)=bd(y)=6

(y)=cd(z)=8

(z)=c(c,y)是安全邊，d(y)=6是所有當前樹A之外的點到樹A的最短距離。當邊(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一個點的樹A

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

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

V

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

Q

u

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

A

A

{(

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

(u)=nil時，不操作

V(A)

V(A){u}

//點的集合V(A)多了一個點

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)為頂點集合，以A為邊的樹End22例: 圖示Prim算法逐步求圖9-1的MSTaecbd4751243f69(b)點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)點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)點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)點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)點c被選，無點須更新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)點f被選，無點須更新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來存儲d(v)，v

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

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