计算机算法基础 第2版 课件 第9章 图的最小支撑树

1第9

章

图的最小支撑树什么是图的最小支撑树

2一个通用的贪心法策略

4Kruskal算法

11Prim算法

181.什么是图的最小支撑树无向图G的一个子图，如果包含所有顶点，则称为G的一个支撑子图无向图G的一个支撑子图，如果是一棵树，则称为图G的一棵支撑树。连通的无向图才有支撑树。加权图G的一棵支撑树T称为最小支撑树(minimumspanningtree，简称MST)，如果它的边的总权值，记作W(T)，是所有支撑树中最小的。讨论如何为连通的加权无向图G找出最小支撑树的算法问题很多应用问题可建模为找MST的问题。23例：(a)

一个连通的加权无向图Gaecbd4751243(c)

一个非最小的支撑树，权值=16aecbd7513(d)

一个最小支撑树，权值=10aecbd1243(b)

一个支撑子图aecbd475124

设连通加权图G(V,E)中，|V|=n，|E|=m，步骤如下：第一步，初始化边的集合A。 //含n个孤立顶点第二步，在E中找出一条边e使得集合A{e}包含在某个MST中。第三步，如果当前的A形成一个支撑树，也就是含n-1条边，算法停止，A

是一个MST。否则，重复第二步。Kruskal和Prim算法都遵循这一策略。显然，主要问题是在第二步中，如何找到这样的边。这条边称为安全边。2.一个通用的贪心法策略5通用算法的伪码Generic-MST(G(V,E))A

ConstructgraphT(V,A) //初始，T含n个顶点，没有边fork1to

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)中权值最小的边称为最小交叉边。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)，权值为w(b,g)=2。8定理9.1

A

E是E的一个子集且包含在某个MST中。如果有一个割C=(P,V-P)与A不相交，那么它的最小交叉边是一条安全边。证明：

我们只需证明

A

{(u,v)}包含在某一个MST中。假设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 证明(继续)10定理9.1意味着最小支撑树的通用算法是正确的。这是因为：1. 因为|V|=n，只要

|A|<

n-1，导出的图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是一个加权的连通图A

//集合A初始化为空集ConstructgraphT(V,A) //初始时，T含有n个孤立顶点Sortedgessuchthate1

e2

…

em

//图G的边按权值排序

for

i

1to

m

//逐条边检查并做取舍选择

if

A

{ei}hasnocycle

//把边ei加到A中不产生回路

then

A

A

{ei} //那么就把ei

选上并加到A中

endif

//否则，边ei加到A中会产生回路endforreturn

T(V,A)

//由顶点集合V和边集合A构成的图就是MSTEnd3.Kruskal算法12正确性证明：归纳法证明:算法每一次对ei(1

i

m)的取舍都是正确的，而且使T(V,A)包含在一个MST中。归纳基础：当i=0时，集合A为空集，T(V,A)显然包含在任一个MST中。归纳步骤：假设算法对前i-1条边做了正确选择，这时的T(V,A)包含在某个MST中。我们证明算法对边ei

的决定也是正确的。分两种情况。算法不选取边ei。这说明，把

ei加到子图A中后产生回路。因为任何树不含回路，既然前面选取的边是正确的，那么

ei

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

不可能是任何尊重A的割的交叉边，所以ei不可取。(接下页)13正确性证明(継续)算法选取边ei。这说明，ei

A无回路。假设ei=(u,v)。在ei

之前，u和v在T(V,A)中必分属不同连通分支。可构造割C

=(P,V-P)，其中P含有所有与顶点u连通的点。显然，C

与A不相交，C

尊重A。ei

必定是最小交叉边，因为权值比ei

小的边都已检查过，要么已被选在集合A中，要么已被丢弃。被丢弃的边不可能是交叉边，因为他们与A中边形成回路，不可能与割C相交。根据定理9.1，ei=(u,v)是个安全边。归纳成功。所以，算法结束时，T(V,A)属于一个MST。这时，T(V,A)必定是个连通图，否则，运算中一定丢弃了一条连结不同分支的边，这与算法矛盾。因为T(V,A)含n个顶点，它就是一个MST。14算法复杂度边的排序需要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分属的两连通分支就合成一个分支了，需要把它们对应的集合并为一个集合并保留一个分支号。我们用Union(u,v)表示这个操作。Union-Find

算法对m条边的操作复杂度是O(m

(n))。

(n)是Ackermann函数的反函数，增长极慢，可认为常数。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算法复杂度是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的边只形成一个连通分支，即一棵正在逐步发展的树，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关联的交叉边中权值最小的边。

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 //使下面第一次循环产生只含s一个点的树A

//边的集合初始为空V(A)

//顶点集合V(A)初始为空Q

V

//以d(v)为关键字，用Q把所有点v组织起来while

Q

u

Extract-Min(Q) //d(u)值最小并从Q中剥离，修复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)和修复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)初始状态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算法复杂度复杂度取决于用什么数据结构Q来存儲d(v)，v

V。用数组作为Q。算法主要部分是while循环，进行n次，每次做两件事。一是找出最小d(u)，并把边(

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