计算机算法基础 第2版 习题及答案汇 沈孝钧 第9-17章

PAGE2第9章 图的最小支撑树以图9-6为例，图示用Kruskal算法逐步计算下面各图的最小支撑树。解：(a)aab66dfcg412810539137e(1)66adbfcg412810539137e(2)666adbfcg412810539137e(3)66adbfcg412810539137e(4)666adbfcg412810539137e(5)66adbfcg412810539137e(6)666adbfcg412810539137e(7)66adbfcg412810539137e(8)666adbfcg412810539137e(9)66adbfcg412810539137e(10)666adbfcg412810539137e(11)66adbfcg4537e(12)算法产生的MST(b)4412adbfcg7561114312910e13(1)h412adbfcg7561114312910e13(2)h4412adbfcg7561114312910e13(3)h412adbfcg7561114312910e13(4)h4412adbfcg7561114312910e13(5)h412adbfcg7561114312910e13(6)h4412adbfcg7561114312910e13(7)h412adbfcg7561114312910e13(8)h4412adbfcg7561114312910e13(9)h412adbfcg7561114312910e13(10)h4412adbfcg7561114312910e13(11)h412adbfcg7561114312910e13(12)h4412adbfcg75639e(13)最后的MSTh以图9-8为例，图示用Prim算法逐步计算下面各图的最小支撑树。我们假设起始点为a。66adbfcg5981010h4137e(b)88766116adbfcg498105h11137e(a)9677解：(a)66d=0=niladbfcg498105h11137e(0)初始化967d==nild==nild==nild==nild==nild==nild==nil76d=0=niladbfcg498105h11137e(1)选a，更新b，c，d，e967d=5=ad==nild==nild==nild=13=ad=6=ad=9=a766d=0=niladbfcg498105h11137e(2)选d，更新e，f967d=5=ad=11=dd==nild==nild=13=ad=6=ad=7=d76d=0=niladbfcg498105h11137e(3)选b，更新c967d=5=ad=11=dd==nild==nild=10=bd=6=ad=7=d766d=0=niladbfcg498105h11137e(4)选e，更新c，f，g967d=5=ad=9=ed==nild=6=ed=7=ed=6=ad=7=d76d=0=niladbfcg498105h11137e(5)选g，更新f，h967d=5=ad=8=gd=7=gd=6=ed=7=ed=6=ad=7=d766d=0=niladbfcg498105h11137e(6)选c，没有更新点967d=5=ad=8=gd=7=gd=6=ed=7=ed=6=ad=7=d76d=0=niladbfcg498105h11137e(7)选h，更新f967d=5=ad=4=hd=7=gd=6=ed=7=ed=6=ad=7=d766d=0=niladbfcg498105h11137e(8)选f，没有更新点967d=5=ad=4=hd=7=gd=6=ed=7=ed=6=ad=7=d7adbfcg45h7e(9)最后的MST，总权值为426776(b)66adbfcg5981010h4137e(0)初始化8876611d==nild==nild==nild==nild=0=nild==nild==nild==nil6adbfcg5981010h4137e(1)选a，更新b，c，g8876611d=10=ad==nild==nild==nild=0=nild=4=ad=11=ad==nil66adbfcg5981010h4137e(2)选c，更新b，d，g，h8876611d=9=cd==nild==nild=6=cd=0=nild=4=ad=10=cd=8=c6adbfcg5981010h4137e(3)选h，更新g，f8876611d=9=cd==nild=13=hd=6=cd=0=nild=4=ad=7=hd=8=c66adbfcg5981010h4137e(4)选g，更新e8876611d=9=cd=6=gd=13=hd=6=cd=0=nild=4=ad=7=hd=8=c(5)选e，更新b，d，f6adbfcg5981010h4137e8876611d=8=ed=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e66adbfcg5981010h4137e(6)选f，无更新点8876611d=8=ed=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e6adbfcg5981010h4137e(7)选d，更新b8876611d=7=dd=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e66adbfcg5981010h4137e(8)选b，无更新点8876611d=7=dd=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e6adbfcg5h47e(9)最后的MST，总权值为41766我们知道，如果一图中所有边的权都一样，那么任何一个支撑树都是一个最小支撑树并且可以用广度优先或者深度优先算法求得。现在，假设图G(V,E)中边的权不完全一样，但是只有两种，要么是w(>0)或者是2w。有个教授提出下面的算法：Smart-MST(G(V,E))在每一条有权2w的边(u,v)中间插入一新点p，把边(u,v)变成两条边，(u,p)和(p,v)，并给每条边以权值w，即w(u,p)=w(p,v)=w。我们把这个改变后的图记为G’。用BFS算出G’的支撑树T’。把T’中所有在第一步新插入的点去掉，即再把(u,p)和(p,v)并为一条边(u,v)。剩下的图为G的MST。请证明这个算法正确或证明不正确。解：这个算法不正确。下面图给出一反例。下图(a)是原图G，图(b)是在每条权为2w的边中插入一点后的图G’，图(c)是用BFS后得到的支撑树T’。显然，把插入点移走后的T’不是MST。ww2wwacbwwwacb·wwwacb·w(a)(b)(c)假设边(u,v)是加权的连通图G(V,E)中权值最小的一条边。证明边(u,v)一定会出现在某个最小支撑树中。进一步，如果这条边的权比任何其他的边都绝对地小，即没有另一与之权相等的边，那么，任何一个最小支撑树都含有这个边。证明：考虑以顶点u为一边的割C=({u},V-{u})。因为一开始的子集A为空集，那么这个割显然尊重A。因为边(u,v)的权最小，它必定是一个最小交叉边，因而是一条安全边。根据定理9.1，通用算法第一步就可把边(u,v)选入集合A，所以这条边一定会出现在某个最小支撑树中。进一步，如果这条边的权比任何其他的边都绝对地小，那么，任何一个最小支撑树都含有这个边。我们可以用反证法来证。假设树T是一个MST，它不含边(u,v)。那么把边(u,v)加到这个MST中后形成一回路(见下图)。uuvxT是一个MSTy(u,v)T刪除回路上一条边(x,y)后我们得到一个支撑树T’，T’=T{(u,v)}-{(x,y)}。因为(u,v)权最小，w(u,v)<w(x,y)，所以有W(T’)=W(T)+w(u,v)-w(x,y)<W(T)。这与T是最小支撑树相矛盾。所以，任何一个最小支撑树都含有这个权最小的边(u,v)。假设C是加权的连通图G(V,E)中的一个回路，边(u,v)是回路中权值最大的一条边，那么一定会有某个最小支撑树不含有边(u,v)。证明： 假设T是连通图G(V,E)的一个最小支撑树。如果T不含有边(u,v)，则证明完成。所以，为了用反证法，我们假定T含有边(u,v)。现在，如果我们把边(u,v)从T中删除，则把T分裂为两个不相交的子树T1和T2，而且u和v分属两边。不坊设uT1，vT2(见下图(a))。再考虑把边(u,v)从回路C中去掉后的路径，P=C–{(u,v)}，它的两端为u和v。如果我们沿着路径P从顶点u到顶点v走的话，一定会碰上一条边(x,y)使得xT1，yT2(见下图(b))。显然T’=(T–{(u,v)}{(x,y)}也是一个支撑树。因为w(x,y)≤w(u,v)，我们有W(T’)=W(T)-w(u,v)+w(x,y)≤W(T)。所以T’也必定是一个最小支撑树，否则矛盾。因为T’不含有边(u,v)，命题得证。(a)设计一个计算加权连通图G(V,E)的最小支撑树T的算法使它含有图中某一条指定的边(a,b)。也就是说，T是所有含边(a,b)的支撑树中权值最小的一个。你需要证明其正确性。(b)设计一个计算加权连通图G(V,E)的最小支撑树T的算法使它含有图中一个边的子集A。其中，子集A不包含回路。也就是说，T是所有含子集A的支撑树中权值最小的一个。你需要证明其正确性。解: (a)算法如下：MST-Variation-1(G(V,E),a,b) //边(a,b)Ez¬min{w(u,v)|(u,v)ÎE} //找出边里面最小的权值zk¬w(a,b) //k是边(a,b)的权值，显然有zkw(a,b)¬z–1 //把边(a,b)的权值改为z-1后，它的权值最小用Kruskal或Prim算法找出变更后的图G’的MST //w(a,b)=z–1是唯一的变化w(a,b)¬k //恢复w(a,b)原来的值returnMST //这个MST就是解正确性证明：考虑算法第4行中变更后的图G’，它与图G的唯一区别是边(a,b)的权值不同。在图G’中，边(a,b)的权值是w’(a,b)=z–1。让我们用T’表示图G’的最小支撑树；用T表示算法产生的支撑树；用T*表示原图G的任一个含边(a,b)的支撑树。我们需要证明：边(a,b)一定在T中。W(T)W(T*)。先证明(1)。算法的第4行得到图G’的最小支撑树T’，因为w’(a,b)=z–1有最小的权值，习题4证明了边(a,b)一定在T’中。为完整起见，这里再用反证法证一下。假设边(a,b)不在T’中，那么删去T’中从a到b的路径上一条边(x,y)，再把边(a,b)加进来，就得到另一个支撑树T’’(见下图)。因为w’(a,b)=z–1<w(x,y)，所以有W(T’’)=W(T’)-w(x,y)+w’(a,b)<W(T’)。这与T’是MST矛盾，所以边(a,b)一定在T’中，那么，也就在支撑树T中了。接着，我们证明(2)。假设T*是原图G的任何一个含边(a,b)的支撑树。如果我们把T*里的边(a,b)的权值换为(z–1)，那么T*就变成一个G’的的支撑树，但不一定是最小。因为T’是图G’的MST，所以有W(T’)W(T*)–k+(z–1) (1)因为算法产生的支撑树T是把T’中边(a,b)的权值换为k，所以有W(T)=W(T’)+k-(z–1) (2)把式(1)代入式(2)，得 :W(T)=W(T’)+k-(z–1)(W(T*)–k+(z–1))+k-(z–1)=W(T*)。(b) 算法如下:MST-Variation-2(G(V,E),A)z¬min{w(u,v)|(u,v)ÎE}G’(V’,E’)¬G(V,E) //复制一个考贝A’¬Aforeachedge(a’,b’)A’ w(a’,b’)¬z–1 //把A’中，也就是A中每条边的权值都变成z–1endfor用Kruskal或Prim算法找到图G’的MST，记为T’T¬foreachedge(a’,b’)inT’ TT{(a,b)} //T是原图中同样边组成的树endforreturnT End正确性证明：显然，算法中，图G’是把集合A中每一条边的权值改为z-1而得到的。首先证明A’一定在T’中。如果其中有任何一条边(a,b)A’不在T’中，那么把(a,b)加到T’中形成一回路。因为A’中边不形成回路，回路中一定会有不在A’中边。那么，和上面(a)部分证明一样，把这条边换为(a,b)后可得权更小的支撑树而矛盾。所以A’T’。从而有AT。假设T*是原图G中任一个含子集A的支撑树。如果我们T*中子集A的每一条边的权值改为z-1，那么我们就得到一个图G’的支撑树，但不一定最小。因为T’是G’的MST，所以有：W(T’)W(T*)-W(A)+|A|(z-1) (1)因为算法产生的支撑树T是把T’中子集A的每一条边的权值从z-1改为它原来的的权值，所以有：W(T)=W(T’)+W(A)-|A|(z-1) (2)把式(1)代入式(2)，得: W(T)=W(T’)+W(A)-|A|(z-1)(W(T*)-W(A)+|A|(z-1))+W(A)-|A|(z-1)=W(T*)。所以，算法产生的支撑树T是所有含子集A的支撑树中权值最小的一个。(a) T和T’是同一个连通图G的两个不同支撑树。假设边x是T的一条边但不是T’里的边。证明在T’中存在一条边y不属T，并且(T-{x}){y}和(T’-{y}){x}都是G的支撑树。(b) 假设一个图G的所有边的权值都两两不等，证明它只能有唯一的一个最小支撑树。证明：(a)假定x=(u，v)。如下图(a)所示，把x从T里刪去后，T分裂为T1和T2两个子树，并且uT1和vT2。 让V1表示T1中顶点的集合，V2表示T2中顶点的集合，那么C=(V1,V2)是一个割。如果我们沿着在T’中从顶点u到顶点v的路径走的话，我们一定会碰到一条穿越这个割的交叉边y=(a,b)使得aV1和bV2。显然(T-{x}){y}构成一个支撑树。把y从T’中刪去后，T’分裂为两个子树，顶点a和b分属两边，并且顶点u和a在同一边，v和b在同一边，而边x=(u,v)连接这两个子树。因此，(T’-{y}){x}也是一个支撑树，证毕。(b) 我们用反证法。假设图G有两个不同的最小支撑树T和T’。因为不同，一定有一条边xT，但xT’。根据(a)题的结果，在T’中存在一条边y不属T，并且(T-{x}){y}和(T’-{y}){x}都是G支撑树。因为G的所有边的权都两两不等，w(x)w(y)。不失一般性，假设w(x)>w(y)。那么，T*=(T-{x}){y}的权值为W(T*)=W(T)–w(x)+w(y)<W(T)。这与T是一个最小支撑树相矛盾。所以，图G只能有唯一的一个最小支撑树。假设图G(V,E)的最小支撑树是T。假设我们把图中一条不在T中的某条边(u,v)(T)的权减少。请设计一个O(n)算法，把T进行适当修改，从而得到对应於上述修改后图的最小支撑树。你需要证明你的算法的正确性。解: 假设边(u,v)T的权w(u,v)减少为w*(u,v)<w(u,v)。修改后的图的最小支撑树可以用下面算法从T得到。MST-for-modified-graph(G,T,w*(u,v))沿着T里面从顶点u到顶点v的唯一路径p(u,v)，逐条边检查找出权值最大的边e。ifw(e)>w*(u,v) thenT*TÈ{(u,v)}–{e} elseT*TendifreturnT*因为算法第一步可以对最小支撑树T作一次从顶点u开始的DFS搜索实现，所以算法的复杂度为O(n)，这里n=|V|。正确性证明：显然，算法输出的T*是按题意修改后图的一棵支撑树。我们用W(T)表示原来图的最小支撑树的总权值，而用W(T*)表示上面算法产生的支撑树的总权值。显然，如果w(e)>w*(u,v)，我们有W(T*)=W(T)+w*(u,v)–w(e)<W(T)，否则有W(T*)=W(T)W(T)+w*(u,v)–w(e)。所以，任何情况下有：W(T*)W(T)和W(T*)W(T)+w*(u,v)–w(e) (1)假设Tmod是修改后的图的任何一个支撑树，我们证明W(T*)W(Tmod)。我们分两种情况讨论如下。Tmod不含边(u,v)。如果是这种情况，Tmod也是图未改动前的一个支撑树，所以必有W(T)W(Tmod)。由上面(1)式，W(T*)W(T)，所以有W(T*)W(Tmod)。Tmod含有边(u,v)。如果是这种情况，如下图所示，我们把边(u,v)从Tmod删除以后会得到两个不相交子树T1和T2。那么，在原图G的最小支撑树T里面，从顶点u到顶点v的唯一路径p(u,v)上一定含有一条边(a,b)使得aÎT1和bÎT2。这条边加上T1和T2也形成一个支撑图T’={(a,b)}T1T2=TmodÈ{(a,b)}–{(u,v)}，并且有关系W(T’)=W(Tmod)+w(a,b)-w*(u,v)。因为T’不含有边(u,v)，它是原来图中的一个支撑树，所以有W(T)W(T’)，也就是，W(T)W(Tmod)+w(a,b)-w*(u,v) (2)由上面(1)式，我们有W(T*)W(T)+w*(u,v)–w(e)。把(2)式代入后，我们得到：W(T*)W(T)+w*(u,v)–w(e)[W(Tmod)+w(a,b)-w*(u,v)]+w*(u,v)–w(e)=W(Tmod)+w(a,b)-w(e)。W(Tmod) (因为边e也在路径p(u,v)上，且有w(e)w(a,b)。)这就证明了，对于按题意修改后的图的任何一个支撑树Tmod，都有W(T*)W(Tmod)。那么，T*必定是一棵修改后的图的最小支撑树。与最小支撑树对称的一个概念是最大支撑树。一个加权连通图的最大支撑树就是具有最大权值的支撑树。请设计一个时间复杂度好的，计算一个加权连通图G(V,E)的最大支撑树的算法。解: 一个简单算法如下。Maximum-SP(G(V,E))从图G构造图G’。G’是把G中每条边的权值加上负号取得。用Kruskal算法或Prim算法得到G’的最小支撑树T’把T’中每条边的权改回原来的值，即去掉每条边上所加负号，得到图G的支撑树TReturnT因为同样一个支撑树T在图G’中的权是它在图G中的权取反，所以G’的最小支撑树恰恰是G的最大支撑树。所以算法正确。算法复杂度与最小支撑树算法一样。下面是两个计算最小支撑树的算法的伪码。对每一个算法，如果正确，请证明其正确性，并讨论如何有效地实现它；否则，用反例证明其不正确。我们假定图G(V,E)是个加权连通图。MST-A(G(V,E))Sortedgessuchthate1e2…emT¬Efori1tom //按排好顺序依次检查每条边 ifT–{ei}仍是一个连通图 thenT¬T–{ei} endifendforreturnTEndMST-B(G(V,E))T¬foreachedgee,takeninarbitraryorder //以任意顺序逐条边检查 ifTÈ{e}hasnocycles thenT¬TÈ{e} endifendforreturnTEnd解：(a)这个算法正确。我们先用归纳法证明，当算法每次从T中刪去一条边e=(u,v)时，T–{e}仍然含有一个MST。归纳基础：开始时，图G(V,E)是个加权连通图，含有一个MST。所以，在第3行的循环前，T=E含有一个MST。归纳步骤：假设算法从T中刪去k条边后，k0，剩下的图是T’并且含有一个MST。现在证明，如果算法在图T’中再删去一条边e’，T’–{e’}仍然含有一个MST。由算法知，T’–{e’}是个连通图。这意味着T’中有一个含有e’的回路C’。可断定，回路中e’的权值最大。这是因为，如果回路中有比e’的权值大的边，那么它应该在先前被检查过并且被删去。所以，根据第5题的结果，T’–{e’}含有一个MST。归纳成功。由上面证明的结果知，算法输出的T含有一个MST。现在，我们只需证明，T是一棵树即可。这是显然的。首先，T是连通的，因为每一步都保证了T的连通性。第二，T必不含回路。否则，回路中权最大的边在被检查时未被删去，与算法矛盾。因此，最后的T必定是一棵树，那么它必定是一个MST，算法正确。这个算法的第一步可用任一已知的排序算法在O(mlgn)时间完成。检查一个图的连通性可以用BFS或DFS在O(m)时间完成。因为有m条边要检查，这样做，算法需要O(m2)时间。(b)这个算法不正确。下图给出一反例。下图(a)是一个加权的连通图。如果我们按顺序(a,b),(b,c),(c,d),(d,a)检查边的话，会得到一个图(b)中的支撑图。这不是最小支撑树。假设G(V，E)是一个加权的连通图并有|V|=n,|E|=m。又设每条边e上的权为1到W之间的某个整数，1w(e)W，这里W是一个正整数的常数。请设计一个复杂度为O(m)的算法计算图G的最小支撑树。解: 我们采用Prim算法但需要设计一个数据结构Q使得Extract-Min(Q)和更新d(v)可以很快。因为1w(e)W，所以d(v)[0,W]。我们把具有相同权值的顶点组织为一个集合或链表。具体来说，我们定义：L[k]={u|d(u)=k}(0£k£W)和L[W+1]={u|d(u)=¥}。我们用链表把每个集合中顶点链接起来。一开始，L[0]={s}，L[W+1]=V–{s}，L[k]=，kÎ{1,2,…,W}。这些链表的总和组成Q。每当算法需要做Extract-Min(Q)时，我们就顺序搜索L[0]，L[1]，L[2]，…，直到找到一个非空的链表L[k]。那么，这个链表中任一顶点v的d(v)值等于k，并且必定是最小的。我们取出该链表中首项。这一步最多需要查看W+2个链表，时间为O(W)=O(1)。因总共需要做n次循环，这部分总时间为O(n)。当一个顶点u的d(u)值需要从k更新到p<k时，我们只需把顶点u从链表L[k]摘下来，然后挂到链表L[p]上去即可。因此每一次更新只需O(1)时间。因为我们需要最多2m次更新，所以算法的复杂度是O(n)+O(m)=O(m)。下面是该算法伪码。Modified-Prim’s-Algorithm(G(V,E),s)foreachvÎV d(v)¬¥ p(v)¬nil mark(v)F //表示点v还没有加入到树A中endfor d(s)¬0A¬ ConstructT(V,A)fork1toW L[k]¬ //初始化链表，建立指向链表L[k]的指针，首项为空endforL[0]¬{s}L[W+1]V–{s}forj1ton //循环n次，每次取一个顶点和一条边 i¬0 whileL[i]=Æ i¬i+1 endwhile u¬ExtractheadfromL[i] //从L[i]中删除首项 A¬AÈ{(p(u),u)} //如果p(u)=nil，A不变，否则，A加一条安全边 mark(u)T foreachvÎAdj(u) ifmark(v)=Fandw(u,v)<d(v) //更新u的邻居v then p(v)¬u k¬d(v) L[k]¬L[k]-{v} //从L[k]中删除点v d(v)¬p¬w(u,v) //更新d(v) L[p]¬L[p]È{v} //在L[p]尾部插入点v endif endforendforreturnT(V,A)End根据上面讨论，该算法的时间复杂度是O(m)。(最宽路径问题)在加权连通图G(V,E)的一条路径上权值最小的一条边称为这条路径的瓶颈，而这条路径的宽度定义为它的一条瓶颈边的权值。例如，下图中路径<a,b,e,g>的瓶颈是边(b,e)，这条路径的宽度为w(b,e)=7。图G(V,E)中从顶点u到顶点v的所有路径中宽度最大的一条路径称为从u到v的最宽路径。例如下图中从a到g的最宽路径是<a,b,c,d,f,g>，其宽度是8。假设T是G(V,E)的最大支撑树(定义见第9题)，证明T中任意两点之间的路径都是G(V,E)中这两点间的最宽路径。证明：为了用反证法证明，假设P(u,v)是T中一条从顶点u到顶点v的路径但不是G中从u到v的最宽路径，而路径P*(u,v)才是最宽路径。我们证明这会导致矛盾。假设边(x,y)和边(x*,y*)分别是P(u,v)和P*(u,v)的瓶颈。那么，必有关系w(x,y)<w(x*,y*)≤P*(u,v)上任一条边的权。如下图所示，如果我们把边(x,y)从T中删除，T便分裂为两个不相交子树T1和T2，并且假设x和u属於T1而y和v属於T2。那么，路径P*(u,v)必定经过一条连接T1和T2的边(a,b)。那么，T’=T1T2{(a,b)}便是一个支撑树并有权值W(T’)=W(T1)+W(T2)+w(a,b)=W(T1)+W(T2)+w(x,y)+[w(a,b)-w(x,y)]=W(T)+[w(a,b)-w(x,y)]因为路径P*(u,v)的宽度比P(u,v)宽，我们有w(x,y)<w(a,b)，从而有W(T’)=W(T)+[w(a,b)-w(x,y)]>W(T)，这与T是最大支撑树矛盾。重新考虑第11题，不同的是，题中W不再是常数，而是一个任意的正整数。我们把题目重述如下。假设G=(V,E)是一个加权的连通图并有|V|=n,|E|=m。又设每条边e上的权为1到W之间的某个整数，1w(e)W，这里W是一个任意的正整数。修改Prim算法使得最小支撑树可以在O(nW+m)时间内算出。*解释如何设计一个O(mlgW)算法找到这个图的最小支撑树(不需详细伪码)。(提示：用红黑树。)解:(a) 算法与第11题的解相同。我们重写在下面，但复杂度的分析不同。我们定义集合L[k]={u|d(u)=k}(0£k£W)和L[W+1]={u|d(u)=¥}。我们用链表把每个集合中顶点链接起来。一开始，L[0]={s}，L[W+1]=V–{s}，L[k]=，kÎ{1,2,…,W}。这些链表的总和组成Q。每当算法需要做Extract-Min(Q)时，我们就顺序搜索L[0]，L[1]，L[2]，…，直到找到一个非空的链表L[k]。那么，这个链表中任一顶点v的d(v)值必定是k，并且是最小的。我们取出该链表中首项。这一步最多须要查W+2个链表，时间为O(W)。因总共需要做n次循环，这部分总时间为O(nW)。当一个顶点u的d(u)值需要从k更新到p<k时，我们只需把顶点u从链表L[k]摘下来，然后挂到链表L[p]上去即可。因此每一次更新只需O(1)时间。因为一共有O(m)个更新操作，所以算法的复杂度为O(nW+m)。下面是该算法伪码。Modified-Prim’s-algorithm(G(V,E),s)foreachvÎV d(v)¬¥ p(v)¬nil mark(v)Fendford(s)¬0A¬ ConstructT(V,A)fork=1toW L[k]¬ //初始化链表，建立指向链表L[k]的指针，首项为空endforL[0]¬{s}L[W+1]=V–{s}forj1ton i¬0 whileL[i]=Æ i¬i+1 endwhile u¬ExtractheadfromL[i] //从L[i]中删除首项 A¬AÈ{(p(u),u)} //加一条安全边。u=s时，p(u)=nil，不操作 mark(u)T foreachvÎAdj(u) ifmark(v)=Fandw(u,v)<d(v) //更新u的邻居v then p(v)¬u k¬d(v) L[k]¬L[k]-{v} //从L[k]中删除点v d(v)¬p¬w(u,v) L[p]¬L[p]È{v} //在L[k]尾部插入点v endif endforendforreturnT(V,A)End(b) 如果照上面(a)部分做法，为每一个权值k，建一个链表L[k](0£k£W+1)那么算法复杂度至少是(W)。因为W可以是任意大正数，这样做不能满足O(nlgW)要求。所以，我们的做法是，仅当权值k确实出现在某条边上，才建链表L[k]。我们用红黑树（参见附录A）作为数据结构。如果树中有W个内结点，那么红黑树可以在O(lgW)时间内完成以下操作：寻找红黑树里是否有结点含有关键字x，RB-Search(T,x)插入一个关键字x，RB-Insert(T,x)删除一个关键字x，RB-Delete(T,x)寻找红黑树里最小的关键字x，RB-min(T,x)初始时，我们建立两个链表：L[0]¬{s}L[]=V–{s}。这里L[k]表示是所有d(v)=k的顶点组成的链表。然后初始化红黑树T，使它含有两个内结点，一个含有指向L[0]的指针，另一个含有指向L[]的指针。其它的初始化与上面(a)部分同。当我们需要Extract-min(Q)时，我们可如下操作：kRB-min(T,x)uheadofL[k] //链表L[k]首项对应顶点udeleteufromL[k] //把顶点u从L[k]删除ifL[k]= thenRB-Delete(T,k) //这时，T(V,A)之外没有d(v)=k的顶点endif当我们需要把顶点v的d(v)值，从d(v)=k更新为d(v)=p时，p<k，我们可如下操作：deletevfromL[k]ifL[k]= thenRB-Delete(T,k)endififRB-Search(T,p)=true //红黑树中有指向L[p]的指针，L[p]非空 then L[p]L[p]{v} //插入点v else L[p] //建立并初始化链表L[p] L[p]L[p]{v} //含一个顶点v RB-Insert(T,p) //红黑树中插入指向L[p]的指针endif由以上讨论可见，红黑树里结点都指向不同的链表，所以内结点的个数最多是W，当然，也不会大于m。再有，每个操作，不论是Extract-min(Q)还是更新d(v)，都需要最多O(lgW)时间。因为总共有n个Extract-min(Q)操作和O(m)个更新操作，所以算法的复杂度为O(nlgW+mlgW)=O(mlgW)。如果加权连通图G(V,E)的一个支撑子图由k棵树组成，则称为k-树支撑森林。一个支撑树则是k=1时支撑森林的一个特殊情况。最小k-树支撑森林是具有最小权值的一个k-树支撑森林。证明下面计算最小2-树支撑森林的算法正确Minimum-2-Tree-Spanning-Forest(G(V,E))用Kruskal或Prim算法计算G(V,E)的一个最小支撑树T找出T中有最大权值的边eFT–{e}returnFEnd请设计一个高时效的计算图G(V,E)的最小k-树支撑森林(k2)的算法并证明其正确性和分析其复杂度。解: (a)我们用反证法证明。假设T和F分别是上面算法得到的最小支撑树和2-树支撑森林，但F的权值不是最小的。设最小2-树支撑森林是F*，它含有两个树T1和T2，并有W(F)>W(T1)+W(T2)。T1和T2对应了一个顶点的分割C={P,V-P}，其中P包含T1中的所有顶点，而V-P包含T2中的所有顶点。设E*为所有交叉边的集合，即E*={(u,v)E|uT1，vT2}。那么，因T中有从T1中点到T2中点的路径，E*必定含有一条T里的边。假设边(u,v)T并且(u,v)E*。那么，T*=T1T2{(u,v)}是G的一个支撑树。因为w(u,v)w(e)，所以有W(T*)=W(T1)+W(T2)+w(u,v)<W(F)+w(e)=W(T)。这与T是最小支撑树相矛盾。所以算法正确。(b)Minimum-k-Tree-Spanning-Forest(G(V,E)) //kn1 用Kruskal或Prim算法计算G(V,E)的一个最小支撑树T2 找出T中(k-1)条有最大权值的边e1,e2,…,ek-13 FT–{e1,e2,…,ek-1}4. ReturnF正确性证明：我们对k进行归纳证明。归纳基础:问题(a)证明了k=2的情况。归纳步骤:假定对最小(k-1)-树的支撑森林，k3，上面算法都能正确计算，我们证明上面算法也能正确算出最小k-树的支撑森林。假设T和F分别是上面算法得到的最小支撑树和k-树支撑森林，但F的权值不是最小的。假设最小k-树支撑森林是F*，它的k个树为T1,T2,…,Tk。我们将证明W(F)W(T1)+W(T2)+…+W(Tk)=W(F*)。我们用E*表示子树T1,T2,…,Tk之间的所有边的集合，即E*={(u,v)E|uTi和vTj,1i,jk,ij}。那么，E*必定有(k-1)条在T里的边。这是因为T1,T2,…,Tk把G的顶点分割为k个集合，所以至少要k-1条边才可以把它们连结成一棵树。所以|E*T|(k-1)。假定边(u,v)是E*T中权值最小的边。因为上面算法中刪去的是树T中权值最大的(k-1)条边，e1,e2,…,ek-1，且满足w(e1)w(e2)…w(ek-1)，所以我们有w(u,v)w(ek-1)。因为F*{(u,v)}=T1T2…Tk{(u,v)}形成一个(k-1)-树支撑森林，由归纳假没，F{ek-1}是一个最小(k-1)-树支撑森林，所以有W(F{ek-1})W(F*{(u,v)})。也就是W(F)+w(ek-1)W(F*)+w(u,v)。所以有：W(F)W(F*)+w(u,v)-w(ek-1)。因为w(u,v)w(ek-1)，所以有W(F)W(F*)。证毕。算法第二步从n个数中找k个最大的数可以用第5.4.3节的方法在O(n+klgn)=O(nlgn)时间内完成，因此，算法复杂度与计算最小支撑树相同。加权连通图G(V,E)的一个支撑树的瓶颈边是这棵树中有最大权值的一条边，其权值称为这个树的瓶颈值。如果一个支撑树的瓶颈值是G的所有支撑树中最小的，那么这个支撑树称为瓶颈支撑树，记为BT(G)。证明最小支撑树也是一个瓶颈支撑树。设计一个线性时间的算法以决定给定的加权连通图G(V,E)是否有瓶颈值不大于b的支撑树。*解释如何设计一个线性时间的算法找出加权连通图G(V,E)的瓶颈支撑树。不要求伪码。解:证明：我们用BN(T)表示树T的瓶颈值。假设T是图G(V,E)的最小支撑树，而BT是G的瓶颈支撑树。假设T和BT的瓶颈边分别是(u,v)和(a,b)，我们要证明w(u,v)w(a,b)，即BN(T)BN(BT)。为了用反证法证明，我们假定w(u,v)>w(a,b)，并证明导致矛盾。我们把边(u,v)从T中刪去后，T分裂为不相交的两个子树T1和T2，uT1，vT2。让U表示在T1中顶点的集合，V-U表示在T2中顶点的集合，那么C=(U，V-U)是V的一个割(见下图)。UUV-UuvxyT1T2因为w(u,v)>w(a,b)，边(u,v)BT。那么，如果我们沿着BT中从顶点u到顶点v的路径走，一定会碰到一条边(x,y)，其中xU，yV-U。把边(x,y)加到T1和T2中，我们得到一个支撑树T*，T*=T1T2{(x,y)}=T{(x,y)}–{(u,v)}。它的权值是W(T*)=W(T)+w(x,y)–w(u,v)。 因为在BT中，边(a,b)的权最大，而反证假设w(u,v)>w(a,b)，所以有w(u,v)>w(a,b)w(x,y)。因此有W(T*)=W(T)+w(x,y)–w(u,v)<W(T)。这与T是最小支撑树相矛盾。设计一个线性时间的算法以决定给定的加权连通图G(V,E)是否有瓶颈值不大于b的支撑树。算法如下，其正确性一目了然。Exist-BT(G(V,E),b)foreachedgeeE ifw(e)>b thenEE–{e} endifendforSelectavertexsinVBFS(G(V,E),s) //从点s开始作广度优先搜索，产生BFS树foreachvV ifcolor(v)=White thenreturn(nospanningtreeTwithBN(T)b) endifendforBTBFStreereturnBTEnd因为只需一轮BFS，算法的时间复杂度为O(m)。*解释如何设计一个线性时间的算法找出加权连通图G(V,E)的瓶颈支撑树。不要求伪码。算法的思路是用二元搜索找出最小瓶颈支撑树T的BN(T)值。递归算法如下：BN(G(V,E))如果E中所有边有相同权值b，停止并报告BN(G(V,E))=b。(递归见底)找出E中边的权值的中位数。假设边e的权值为中位数，w(e)=b。E1E中权值小于b的边。E2E中权值等于b的边。E3E中权值大于b的边。如果图G(V,E1)有BFS树，则G(V,E)G(V,E1)。否则，如果图G(V,E1E2)有BFS树，则停止并报告BN(G(V,E))=b。否则，如下操作：设图G(V,E1E2)有BFS森林，含有k个树，T1,T2,…,Tk，也称为分支。(8.1) 为每个G中顶点u打上分支号，分支(u)。(8.2) 构造分支图中的点集合，V’={1,2,…,k}，顶点i(1ik)代表分支i。(8.3) 构造分支图中的边，E’={(分支(u),分支(v))|分支(u)分支(v)，(u,v)E3}。(8.4) V’中两点间可能有多条边，只保留一条有最小权值的边。办法是把所有E’中边排序使得(i,j)<(u,v)如果i<u或者i=u但是j<v。显然用计数排序O(n)=O(m)可完成。这样一来，两点间的多条边在序列中就连在一起了，扫描这一序列一遍就可为两点间保留一条有最小权值的边。(8.5) G(V’,E’)是分支图。G(V,E)G(V’,E’)。递归调用BN(G(V,E))。因为|E1|<m/2，|E3|<m/2，我们有递推关系：T(m)<T(m/2)+cm。所以，该算法的复杂度是T(m)=(m)。找出最小瓶颈支撑树T的BN(T)值以后，只需一次BFS搜索就可以找出最小瓶颈支撑树T。假设连通图G的边可以是任意的权值，可正可负。请设计一个找最小支撑连通子图的算法，使其复杂度与最小支撑树一样。请证明算法的正确性。注意，最小支撑连通子图可能比最小支撑树的边多却有更小的总权值。下图给出了一个例子。aabcd-2-1-346有正负权值的连通图Gabcd-2-34G的最小支撑树abcd-2-34G的最小支撑连通子图-1解： Minimum-Spanning-Connected-Subgraph(G(V,E))SelectavertexsVT(V,A)MST-Prim(G(V,E),s) //先算出一个MSTA’AforeachedgeeE ifw(e)<0andeA’ then A’A’{e} //把所有负值边全包进来 endifendforreturnT’(V,A’) //T’(V,A’)是把所有负值边全包进来后的图End正确性证明：我们用反证法证明。假设最小支撑连通子图G’(V,E’)的权值比T’(V,A’)小，W(G’)<W(T’)。显然，G’必定含有所有负权值的边，否则不会最小。我们把所有T’(V,A’)的边分为3个集合：S1: 算法第2步中得到的最小支撑树T(V,A)中有正权值的边的集合。因为W(G’)<W(T’)，S1非空。S2: 算法第2步中得到的最小支撑树T(V,A)中有负权值的边的集合。由顶点V和S2中边形成的子图G(V,S2)必不连通，否则第2步中得到的最小支撑树T(V,A)必不含有正权值的边，与S1非空矛盾。因此S2中边形成若干个连通分支，C1,C2,…,Ck(k>1)，并且每个分支是一棵树。S3: 算法第3步以后加入A’中的边的集合。我们断言，任一条S3中的边一定在上述某个分支内，而不会连接两个分支，否则可找到有比T(V,A)更小权值的支撑树而矛盾。显然G’中边也包含S2和S3，因为它要包含所有负权值的边。S2S3是所有负权值的边的集合。因此，G’中边包含连通分支，C1,C2,…,Ck。我们把S3从G’中删去，得到图G’’=(V,E’-S3)。那么，我们断言G’’必定是个连通图，这是因为任一条S3中的边一定在某个分支内，而不会连接两个分支，所以删除S3中的边不会改变G’的连通性，所以图G’’是连通的。因此G’’有最小支撑树T’’并且T’’必定包含S2中所有边。这是因为S2中所有边不形成回路。因为T’’包含了G’’中所有负权值的边，和一部分正权值的边，所以有W(T’’)≤W(G’’)。因为T(V,A)是G的最小支撑树，G’’G，我们有：W(T(V,A))≤W(T’’)≤W(G’’)，因此有W(T’(V,A’))=W(T(V,A))+W(S3)≤W(G’’)+W(S3)=W(G’)，与假设矛盾。无向连通图的一棵支撑树再加上一条边称为一棵1-树。下面图显示了一个1-树的例子。(a)(a)一个无向图G(b)G的一棵1-树abcdebcdea一个加权的无向连通图G(V,E)的一棵1-树称为最小1-树，如果它有最小的总权值。请设计一个复杂度好的计算最小1-树的算法。你需要证明其正确性和分析复杂度。解： Minimum-1-Tree(G(V,E)) SelectavertexsVT(V,A)MST-Prim(G(V,E),s) //用Prim算法找出一个最小支撑树TE’E–A //不在T里的剩余的边集合ifE’= thenreturn(no1-treeexists) //1-树不存在 else findeE’suchthatw(e)=min{w(e)|eE’} //E’中最小边e returnT{e}endifEnd这个算法显然有与Prim算法相同的复杂度。正确性证明：首先，如果集合E’是空集，那么1-树不可能存在。所以假定E’。我们证明算法产生的T{e}必定是最小1-树。假设T’{e’}是任意一个1-树。因为T’{e’}含有一个回路C，那么C上必有一条边e’’不属於A而属于E’。把这条边从这个1-树中刪去后得到一个支撑树T’’，并且有权值为w(T’’)=w(T’)+w(e’)-w(e’’)。显然也有w(T’)+w(e’)=w(T’’)+w(e’’)。那么，我们有如下关系：w(e’’)w(e) 因为e’’E’=E–A。w(T’’)w(T) 因为T和T’’都是G的支撑树,但T是最小支撑树。所以，我们有w(T’)+w(e’)=w(T’’)+w(e’’)w(T)+w(e)。这也就是说，任一棵1-树的权值都大于等于算法产生的1-树的权值，所以算法正确。假设T是图G(V,E)的一棵以顶点s为根的最小支撑树。如果我们把图G(V,E)中的一条边(u,v)的权值增加到w(u,v)，而这条边也是T中的一条边，(u,v)T，那么T就不一定是这个变化后的图G(V,E)的一棵最小支撑树了。请设计一个O(m)的算法把T修改为变化后的图G(V,E)的一个最小支撑树并证明其正确性。解: 我们的做法是，把边(u,v)从树T里删去，得到两个子树，T1和T2。T1和T2形成对顶点集合V的分割,C=(U1，U2)，其中U1包含T1中所有顶点，U2包含T2中所有顶点。然后，在图G里找出这个割的最小交叉边e，那么T1T2{e}形成的树就是答案。Modify-MST-Increase-Weight(G(V,E),T,u,v)foreachvV Adj(v) //为树T的每个顶点建邻居集合，初始为空endfor foreachvV if(v)=w //(w,v)是一条边 then Adj(w)Adj(w){v} //w和v互为邻居 Adj(v)Adj(v){w} endifendforTT–{(u,v)} //删除边(u,v)后，T=T1T2。设uT1,vT2BFS(T,u)andcolorallvisitedverticesred //只能访问到T1中点，并着为红色BFS(T,v)andcolorallvisitedverticesblue//只能访问到T2中点，并着为蓝色e(u,v)ww(u,v)foreachedge(x,y)E //找最小交叉边 if(color(x)≠color(y))andw(x,y)<w then e(x,y) ww(x,y) endifendforT’T{e} //也就是T1T2{e}returnT’End正确性证明：设T*是边(u,v)的权值增加后的图G(V,E)的任意一个支撑树。我们证明W(T’)W(T*)，这里，T’是我们算法产生的支撑树。我们分两种情况证明.T*包含边(u,v)。如果是这种情况，我们把边(u,v)从T*中删去后得到子树T1*和T1*。因为T是图G的一棵最小支撑树，所以有W(T1)+W(T2)+w0(u,v)W(T1*)+W(T2*)+w0(u,v)。这里，w0(u,v)是边(u,v)原来的权值。所以有W(T1)+W(T2)W(T1*)+W(T2*)。因为w(e)w(u,v)，这里e是算法得到的割C=(U1，U2)的最小交叉边，其中，U1包含T1中所有顶点，U2包含T2中所有顶点。所以有：W(T1)+W(T2)+w(e)W(T1*)+W(T2*)+w(u,v)，也就是W(T’)W(T*)。T*不包含边(u,v)。如果是这种情况，在T*中，从点u到点v的路径上，一定有一条边(x,y)与割C=(U1，U2)相交。因为边(u,v)是原图中这个割的最小交叉边，w0(u,v)w(x,y)，这里，w0(u,v)是边(u,v)原来的权值。现在，如果把边(x,y)从T*中删去，则会得到子树T1*和T2*，使得点u和点v分属两边。因为，T1*T2*{(u,v)}也是原图G的一棵支撑树，而T是一棵最小支撑树，故有：W(T1)+W(T2)+w0(u,v)W(T1*)+W(T2*)+w0(u,v)。所以有：W(T1)+W(T2)W(T1*)+W(T2*)。因为边e是(u,v)的权值增加后的图G中割C=(U1，U2)的最小交叉边，所以有w(e)w(x,y)。因此有W(T1)+W(T2)+w(e)W(T1*)+W(T2*)+w(x,y)。这就证明了W(T’)W(T*)。因为T有n个点，n-1条边，算法在第14行前只需O(n)时间，而第15行的循环有O(m)的复杂度，所以算法有O(m)的复杂度。假设T是图G(V,E)的一棵最小支撑树。它的边是e1,e2,…,en-1，并有权值顺序为w1w2…wn-1，这里，n=|V|。我们定义T的一个子图Ti(V,Ei)如下。子图Ti(V,Ei)有与T相同的顶点集合V，但它的边是Ei=e1e2…ei，即它的边是由T中权值最小的i条边组成(0in-1)。当i=0时，T0不含有边，只含n个顶点。显然，Ti由n-i个连通分支组成，C1,C2,…,Cn-i，而每个连通分支是一棵T的子树。证明图G(V,E)里，除Ei以外的任一条边e，eE-Ei，如果它连結分属两个不同分支的两个点，那么，它的权值w(e)大于等于wi+1，即w(e)wi+1。证明：为了用反证法，假设有边e=E-Ei，连結C1和C2，但w(e)<wi+1。设e=(a,b)，其中aC1，bC2。因为eEi而且w(e)<wi+1，边e不可能属于T，e{e1,e2,…,en-1}。考虑T中从点a到点b的路径P(a,b)。它必定经过T-Ei中某条边e*，即e*{ei+1,ei+2,…,en-1}。我们有：w(e)<wi+1w(e*)。如果我们把e*从T中删去，把边e加进来，我们会得到一个权值更小的支撑树T’:W(T’)=W(T)-w(e*)+w(e)<W(T)。这与T是最小支撑树矛盾。*假设T是图G(V,E)的一个最小支撑树。它的边是e1,e2,…,en-1，并有权值顺序为w1w2…wn-1，这里，n=|V|。假设T’是图G的另一个支撑树，它的边是e’1,e’2,…,e’n-1，并有权值顺序为w’1w’2…w’n-1。证明wiw’i(1in-1)。(题示：先做第19题。)解：我们对i用归纳法证明。 归纳基础。当i=1时，由19题知，w1w’1。 归纳步骤。假设我们有w1w’1,w2w’2,…,wkw’k(k1)，我们证明必有wk+1w’k+1。我们用反证法。假设有wk+1>w’k+1。我们定义子图Tk(V,Ek)，它的顶点集合V与G相同，边集合是Ek=e1e2…ek，即它的边是由T中权值最小的k条边组成(0kn-1)。当k=0时，T0不含有边，只含n个顶点。显然，Tk有n-k个连通分支，C1,C2,…,Cn-k，每一分支是一棵树。由19题知，任何集合E–Ek中的边e，如果连結不同分支的话，必有w(e)wk+1。因为w’k+1<wk+1，所以边e’k+1必定连結同一分支的两个点。又因为w’1w’2…w’k+1，所以边e’1,e’2,…,e’k也必定是连結同一分支中的点。所以这n-k个分支含有集合S’={e’1,e’2,…,e’k+1}中所有k+1条边。让我们假设这n-k个分支中顶点的个数分别是n1,n2,…,nn-k。因为T’是图G的一个支撑树，不含回路，所以这n-k个分支中能够含有T’中边的个数必定小于等于(n1-1)+(n2-1)+…+(nn-k-1)=n1+n2+…+nn-k–(n–k)=n–(n–k)=k。这就产生了矛盾。所以，必定有wk+1w’k+1，归纳成功。假设T是图G(V,E)的一个最小支撑树。设图中的一条边(u,v)E不属于T，(u,v)T。请设计一个O(n)的算法去修改一下T使得修改后的支撑树含边(u,v)并且有最小权值。你需要证明它的正确性。解：伪码如下，证明随后。Modify-MST(T,u,v)BFS(T,u)andgetaBFStree //从顶点u开始对T作BFS，并得到BFS树w-bv //从顶点v开始，沿着到顶点u的路径，找权值最大边a(v)whileanil ifw(a,b)>w then ww(a,b) xa yb endif ba a(a)endwhileT’(T–{(x,y)}){(u,v)}returnT’End正确性证明：假设T*是含有边(u,v)的一棵支撑树，我们证明有W(T’)W(T*)，这里T’是上面算法产生的支撑树。如果我们把边(u,v)从T*删去，那么如下图(a)所示，得到两个子树，T1*和T2*，顶点u属于T1*，顶点v属于T2*。如果我们沿着最小支撑树T中从顶点u到顶点v的路径走，那么，如图(b)所示，一定会碰到一条边(a,b)，其中，aT1*和bT2*。把边(a,b)从最小支撑树T中删除会得到T的两个子树，T1和T2。因为边(a,b)连接T1*和T2*，那么T1*T2*{(a,b)}是一个支撑树。因为T是最小支撑树，所以有W(T1)+W(T2)+w(a,b)W(T1*)+W(T2*)+w(a,b)。从而有：W(T1)+W(T2)W(T1*)+W(T2*)。因此有：W(T1)+W(T2)+w(u,v)W(T1*)+W(T2*)+w(u,v)=W(T*)。因为，由算法知：W(T’)=W(T)-w(x,y)+w(u,v)=[W(T1)+W(T2)+w(a,b)]-w(x,y)+w(u,v)=W(T1)+W(T2)+w(u,v)+(w(a,b)-w(x,y))W(T1)+W(T2)+w(u,v) //因为由算法知w(a,b)w(x,y)所以有W(T’)W(T*)。这证明了算法的正确性，其复杂度显然是O(n)。假设T是图G(V,E)的一个最小支撑树。我们考虑如何能在O(n2)时间里找到第二小的支撑树。第二小的支撑树指的是所有与T不同的支撑树中权值最小的一个。我们假设G(V,E)T，否则不存在。我们分三个小问题来解决。假设我们的算法需要对一个堆栈S作一系列的Push(S,x)和Pop(S)的操作，其中Push(S,x)表示把数字x压入堆栈S，Pop(S)表示把栈顶的元素弹出。此外，我们的算法需要能够知道当前堆栈S中哪个元素最大，它的数字是多少。请设计一个简单算法，任凭堆栈S如何动态变化，都能在O(1)时间里帮我们找到当前堆栈中这个最大元素。假设T(V,E,r)是一个以顶点r为根的树，树中的每条边有实数权值。我们用M(r,v)表示在从根r到顶点v的路径上的边的最大权值。下图给出了一个例子。rr57-3-6abcdfghiljke9-428910611M(r,a)=5,M(r,b)=9,M(r,c)=5,M(r,d)=5,M(r,e)=11,M(r,f)=-3,M(r,g)=-3,M(r,h)=9,M(r,i)=8,M(r,j)=10,M(r,k)=8,M(r,l)=7.请设计一个O(n)的算法为树中每一个根以外的顶点vV，v≠r，计算M(r,v)，这里n=|V|。我们假定，每个顶点u的父亲已知，是π(u)，根的父亲是π(r)=nil。另外，每个顶点u的儿子们由一个链表组织起来，用“vu’snextson”语句就可以访问顶点u的下一个儿子或第一个儿子。如果u’snextson=nil，则表明顶点u的所有儿子们都已被算法访问过了，或者顶点u是个树叶。请设计一个O(n2)算法为加权连通图G(V,E)找出第二小的支撑树。为简单起见，我们假定图G的所有边的权值都不同，并已知T是图G(V,E)的MST。解: (a) 我们用另外一个堆栈S’来帮忙，使得S’的顶始终指向堆栈S中的最大数。我们假定一开始时，堆栈S和S’都是空的。每当我们操作Push(S,x)或Pop(S)时，我们对堆栈S’作出相应的更新操作。具体做法如下：(1)每次Push(S,x)以后，进行以下操作：ifS’=orxTop(S’) //否则不操作 thenPush(S’,x) //x是堆栈S中最大的数(2)每次Pop(S)以前，进行以下操作： ifS’andTop(S)=Top(S’) //否则不操作 thenPop(S’)正确性证明：我们用归纳法证明，如果堆栈S非空，Top(S’)始终指向堆栈S中的最大数。归纳基础：一开始时，堆栈S和S’都是空的。命题正确。当第一个数压入堆栈S时，这个数也被压入堆栈S’，命题正确。归纳步骤：假设经过k次Push(S,x)或Pop(S)操作后，命题正确。我们证明第(k+1)次操作后，命题仍然正确。我们分两种情况：第(k+1)次操作是Push(S,x)。这种情况下，如果S’=，则表明S=，Push(S’,x)后，命题正确。如果S’，但是x<Top(S’)，说明x不会成为最大数，不需改变S’，堆栈S’的顶指向堆栈S中的最大数仍然正确。如果S’，但是x>Top(S’)，说明x成为最大数，Push(S’,x)后使得堆栈S’的顶指向堆栈S中的最大数x，命题正确。如果S’，但是x=Top(S’)，说明x等于最大数，Push(S’,x)后使得堆栈S’的顶仍然指向堆栈S中的最大数x，命题正确。要注意的一点是，这种情况下，必须再次压入x到堆栈S’。这是因为堆栈S中有两个或多个最大数x时，堆栈S’也必须压入同样多的x。这样，一旦弹出x，堆栈S’也相应弹出x以保证S’的栈顶指向前一个x，否则会错误地指向比x小的数。第(k+1)次操作是Pop(S)。这种情况下，如果S’=，则表明S=，两个堆栈都没有操作，命题正确。如果S’，但是Top(S)Top(S’)，则说明Top(S)不是当前堆栈S中最大数。因此，Pop(S)以后，不需要Pop(S’)，堆栈S’的顶仍指向堆栈S中的最大数。如果S’，但是Top(S)=Top(S’)=x，则说明Top(S)=x是当前堆栈S中最大数，而Top(S’)=x是在把x压入堆栈S时同时压入S’的。因此，Pop(S)以后，堆栈S恢复到把x压入之前的状态，那么，Pop(S’)也正确地把堆栈S’恢复到把x压入之前的状态。所以，在两个堆栈都弹出x之后，由归纳假设，Top(S’)指向当前堆栈S中最大数。归纳成功。(b)我们对树T(V,E)进行从根r开始的DFS搜索。让我们来观察一下DFS所用的堆栈S。显然，在任何时刻，如果栈顶元素是顶点v的话，那么，从栈底到栈顶的元素形成一条从根r到顶点v的路径。那么，M(r,v)就是这条路径上的最大权值。由(a)部分问题的解知，我们可以用另一个堆栈S’在O(1)时间内得到M(r,v)。因此，我们有下面的伪码为每个顶点v算出M(r,v)。Largest-Weight(T,r) SS’ //清空两个堆栈Push(S,r)Push(S’,-) //可以认为边(r,r)有权值w(r,r)=-whileS //开始DFS搜索 uTop(S) //不是弹出，是建立指针 vu’snextson ifv≠nil then Push(S,v) ifw(u,v)≥Top(S’) then Push(S’,w(u,v))//包含三个数,u,v,和w(u,v) e