计算机算法基础 第2版 习题及答案 第8章 .docx

PAGE23

第8章 图的周游算法

假设T是一个边上加了权的有n个顶点的树，而顶点x是其中一个指定的顶点。请设计一个复杂度为O(n)的算法，取名Distance(T,x)，算出从顶点x到其他每一个顶点v的距离d(x,v)。这里，边是无向的，两点间的距离是指这两点间一条简单路径可能有的最小的边的总权值。

解：用BFS或者DFS都可以解。下面是用BFS来解。做法是，我们从顶点x出发进行BFS有哪些信誉好的足球投注网站。在初始化时，给每个顶点v置d(x,v)=?，但置d(x,x)=0。在这个过程中，每当我们从顶点u访问它的一个儿子v时，则更新d(x,v)=d(x,u)+w(u,v)，其中w(u,v)是边(u,v)上的权。因为树T中边的个数m=n-1，所以算法有复杂度是O(n)。正确性显然。

Distance(T,x)

foreachv?T

color(v)=White

d(x,v)??

?(v)?nil //表示父亲指针为空

endfor

d(x,x)?0

Q?? //先把队列清空

Enqueue(Q,s) //将s进队，初始化完成

whileQ??

u?Dequeue(Q) //取出队列首项

foreachv?Adj(u)

ifcolor(v)=White

then color(v)?Gray

d(x,v)?d(x,u)+w(u,v)

?(v)?u

Enqueue(Q,v)

endif

endfor

endwhile

End

假定T=(V,E)是一棵有n个顶点的树，它的每条边(u,v)是无向的，并有正数权值w(u,v)0。它的直径定义为T中最长的一条路径的长度,即Diameter(T)=maxu,v∈∈Vδ(u,v)，这里d(u,v)表示点u和点v之间距离，也就是点u和点v之间一条简单路径可能有的最小的边的总权值。证明下面的算法在O(n)时间里正确算出Diameter(T)。算法中所用函数Distance(T,x)

Diameter(T)

SelectanodexinT //任选一点x

Distance(T,x) //调用第1题的算法为T中每一点v计算d(x,v)

Findnodevsuchthatd(x,v)isthelargest //找出与点x距离最大的点v

Distance(T,v) //再调用第1题的算法为T中每一点u计算d(v,u)

Findnodeusuchthatd(v,u)isthelargest //找出与点v距离最大的点u

ReturnDiameter(T)=d(v,u) //d(v,u)就是直径

End

证明：首先，这个算法的复杂度是O(n)，因为每一步的复杂度为O(n)。我们只需证明其正确性。为了用反证法来证明，我们假设树的直径是d(a,b)并且d(a,b)d(v,u)。因为所有权值为正数，所以a和b必定是树的叶子。如果a=x，(上面算法第1步)那么，因为d(x,v)是所有到x的距离中最大的，我们有d(a,b)=d(x,b)≤d(x,v)≤d(u,v)，产生矛盾。我们可假定a≠x。同理可推出a≠v，b≠x，b≠v。(它们也许等于u)。

现在来看一下算法中第一次调用距离算法得到的BFS树，其顶点x是根。从x到各点的路径中，以d(x,v)最长。设叶子a和b的最小公共祖先是顶点w，也就是从a到x的路径与从b到x的路径第一个相交的点。又设k为叶子a和叶子v的最小公共祖先(见下图)。

x

x

k

b

v

w

a

(a)情况1:顶点k是顶点w的祖先或与点w重合

x

w

v

b

k

a

(b)情况2:顶点w是顶点k的祖先

我们分两种情况讨论：

顶点k是顶点w的祖先或与点w重合。即d(x,k)?d(x,w)。图(a)显示了这种情况。

在这种情况下，我们有d(b,w)≤d(b,k)≤d(v,k)。所以，我们有以下推导:

d(a,b)=d(a,w)+d(b,w)

=d(a,w)+d(b,k)-d(w,k)

?d(a,w)+d(v,k)-d(w,k)

=d(a,k)-d(w,k)+d(v,k)-d(w,k)

=d(a,k)+d(v,k)-2d(w,k)

=d(a,v)-2d(w,k)

≤d(a,v)

≤d(u,v)