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

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)foreachvT color(v)=White d(x,v) (v)nil //表示父亲指针为空endford(x,x)0Q //先把队列清空Enqueue(Q,s) //将s进队，初始化完成whileQ uDequeue(Q) //取出队列首项 foreachvAdj(u) ifcolor(v)=White then color(v)Gray d(x,v)d(x,u)+w(u,v) (v)u Enqueue(Q,v) endif endforendwhileEnd假定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 //任选一点xDistance(T,x) //调用第1题的算法为T中每一点v计算d(x,v)Findnodevsuchthatd(x,v)isthelargest //找出与点x距离最大的点vDistance(T,v) //再调用第1题的算法为T中每一点u计算d(v,u)Findnodeusuchthatd(v,u)isthelargest //找出与点v距离最大的点uReturnDiameter(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的最小公共祖先(见下图)。xxkbvwa(a)情况1:顶点k是顶点w的祖先或与点w重合xwvbka(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)。这与d(a,b)>d(v,u)矛盾。顶点w是顶点k的祖先。即d(x,w)d(x,k)。图(b)显示了这种情况。在这种情况下，我们有d(a,k)≤d(v,k)。所以有以下推导：d(a,b)=d(a,k)+d(k,w)+d(b,w)d(v,k)+d(k,w)+d(b,w)=d(v,w)+d(b,w)=d(v,b)≤d(v,u)这也与d(a,b)>d(v,u)矛盾。所以d(v,u)是直径。当我们用邻接矩阵来表示有n个顶点的图时，大多数图的算法需要(n2)时间，但是也有特例。请考虑下面的问题。一个简单有向图的一个顶点称为是总汇点(universalsink)，如果每一个其他顶点都有一条边指向这个顶点，而它却没有出去的边。也就是说，如果一个顶点的入度是n-1而出度为0，那么这个点称为总汇点。假设我们用邻接矩阵来表示一个简单有向图。请设计一个O(n)的算法来判断这个图是否有总汇点，如果有则输出这个点。解：设A为邻接矩阵，顶点标号为1到n。简单有向图有A[i,i]=0(1in)，即对角线元素为0。顶点i是总汇点的充要条件是:对每一个j(1jn)，都有A[i,j]=0，对每一个k(1kn,ki)，都有A[k,i]=1。这也就是说，第i行的元素都是0。而第i列的元素，除A(i,i)以外，都是1。显然总汇点如果存存，它是唯一的。下面是这题的算法。Universal-Sink(A[1..n,1..n])//A是邻接矩阵且A[i,i]=0(1in)。i1j1whileinandjn ifA[i,j]=0 //检查第i个点的可能性，如A[i,j]=1，则查i+1 then jj+1 else ii+1 endifendwhileifi>n thenreturn(nouniversalsink) elseif(A[i,k]=0foranyk,1kn)and(A[k,i]=1foranyk,ki,1kn) thenreturn(vertexiistheuniversalsink) elsereturn(nouniversalsink) endifendifEnd算法的复杂度显然是O(n)因为在while循环中，指针i和j都只能最多增加n次，而第11行的验证也只需O(n)时间。它的正确性证明如下：While循环的目的是找到一个顶点，它有可能成为总汇点。我们从A[1,1]开始一行一行看。如果在这行中有一个1，那么查下一行。在查下一行时，我们不需从头查起，只需从当前列查起。下面的图解释了这个循环的做法。如下图所示，循环的结果有两种，i>n和i≤n。0000…0111…100…0111…100…00(b)第二种情况：in第i行00…0111…100…0111…100…01(a)第一种情况：i>n11…1第i行如果是第一种情况，i>n，那么不可能存在总汇点，这是因为每一行中都有一元素为1。如果是第二种情况，那么顶点i是唯一的可能。这是因为对应顶点1，2，…，(i-1)的行都有一个元素为1，又因为标号大于i的每一个列中都有一个0出现在第i行之前或出现在第i行之中。因此，我们只需查验顶点i即可。算法第11行完成这一查验工作。用DFS设计一个O(m+n)算法来判定一个无向图是否含有一个奇回路，即有奇数条边的回路。解：我们知道一个无向图没有奇回路的充要条件是可以二着色。所以用书中BFS的二着色算法来做是可以的。这里，题目要求用DFS判断，其做法类似。我们在进行DFS时给顶点用红、蓝着色。先把根着为红色。以后每访问一个新的顶点，就把这点着为与它父亲颜色相反的颜色。当我们发现一条反向边时，则检查这条边的两端是否同色。如果是，则发現一个奇回路。算法包括主程序和子程序。伪码如下，正确性显然。Odd-Cycle(G(V,E)) //主程序foreachuV color(u)White (u)nilEndforfoundfalse //Noodd-cyclehasbeenfoundforeachuV ifcolor(u)=White then Odd-Cycle-Check(u) iffound=true thenreturn(Thereisanoddcycle) endif endifendforreturn(Graphhasnooddcycles)EndOdd-Cycle-Check(s)Color(s)RedS //清空堆栈Push(S,s)whileS uTop(S) //不是弹出，而是建立指针 vu’snextneighborinAdj(u) //u的邻接表中下一个邻居v ifv=nil //u的邻居已全部访问完毕 then Pop(S) //u由栈顶弹出 else ifcolor(v)=White //u的下一个邻居是白色 then color(v)not(color(u))//着相反颜色 Push(S,v) else ifcolor(v)=color(u) then foundtrue return endif endif endifendwhileEnd*重做第2题，但是这次我们允许T=(V,E)的每条边(u,v)的权值可以是任何实数。它的直径仍然定义为图中最长的一条简单路径的加权长度,即Diameter(T)=maxu,v∈∈Vδ(u,v)(可能是负数)。请设计一个O(n)时间的算法算出Diameter(T)。为方便起见，我们假定T是一个根树，顶点s是根。另外，每个内结点u有个儿子的集合Son(u)，类似于Adj(u)。如果Son(u)=，则表明顶点解：我们注意到，如果d(u,v)是直径，那么有两种情况：顶点u是顶点v的祖先，或顶点v是顶点u的祖先。顶点u和顶点v没有直系亲属关系，从点u到点v的路径通过它们的最小公共祖先，点w。不论哪种情况，我们从根s起，对树T=(V,E)作DFS。在DFS进行时，我们在每个内结点u计算以下两个值。从点u到它的子孙中最长的一条路径d1(u)=(u,u1)。其中，点u1属于点u为根的子树。从点u到它的子孙中第2长的一条路径d2(u)=(u,u2)。其中，点u2属于点u为根的子树。当点u回溯到父亲(u)时，如果d2(u)>0，那么d1(u)+d2(u)就是点u为根的子树中经过点u的最长路径，否则，d1(u)就是点u为根的子树中以点u为起点的最长路径。所有这些路径中最长的路径就是本题的解。我们可用一个全局变量(i,j)来记录目前最好的解。下面是伪码，正确性显然。Diameter(T,s,i,j,) //(i,j)是直径- //初始化ijnilS //清空堆栈Push(S,s)whileSuTop(S) //不是弹出，而是建立指针 vu’snextsoninSon(u) //u的儿子表中下一个儿子v ifv=nil //u的儿子已全部访问完毕 then Pop(S) //u由栈顶弹出 ifd2(u)>0 //点u为根的子树中经过u的最长路径 then ifd1(u)+d2(u)> //点u的子树中经过u的最长路径 then d1(u)+d2(u) iu1 ju2 endif else ifd1(u)> //点u的子树中从u开始的最长路径 then d1(u) iu ju1 endif endif if(u)=znil //更新父亲的d1和d2 thenifd1(u)>0 then ifw(z,u)+d1(u)>d1(z) thend1(z)w(z,u)+d1(u) z1u1 elseifw(z,u)+d1(u)>d2(z) thend2(z)w(z,u)+d1(u) z2u1 endif endif else ifw(z,u)>d1(z) thend1(z)w(z,u) z1u else ifw(z,u)>d2(z) thend2(z)w(z,u) z2u endif endif endif endif else //点v还没有被访问 Push(S,v) d1(v) d2(v)- (v)u endifendwhilereturn,i,jEnd假设一个连通的无向图G(V,E)的边只有两种权值，w(>0)或者2w。请设计一个O(m+n)的算法计算从顶点u到顶点v的最短路径。解: 解题思路是，第1步，我们先在每一个有2w权值的边上加上一个点，也就是把这条边一分为二，并且给每条边赋以权值w。这样一来，图中每条边的权值都相等。第2步，我们用广度优先搜索在这个修改后的图G’里找到顶点u到顶点v最短路径。最后，第3步，我们把在第1步中加的点从这条路径上去掉。伪码如下。Shortest-Path(G(V,E),u,v)G(V’,E’)G(V,E)foreveryedge(a,b)E ifw(a,b)=w thenE’¬E’È{(a,b)withweightw} //权为w的边不动 else V’¬VÈ{vab} //加一个新的点vab E’¬E’È{(a,vab)withweightw}È{(vab,b)withweightw} endifendforBFS(G’(V’,E’),u)S //清空堆栈zvwhileznil then Push(S,z) z(z) ifznilandzV thenz(z) //删去不在原图中的顶点 endifendwhile //堆栈中从顶到底的顶点序列就是顶点u到顶点v的最短路径。End堆栈中从顶到底的顶点序列就是顶点u到顶点v的最短路径。这是因为在G中任何一条从u到v的路径对应了一条G’中的一条从u到v的路径。这里，对应指的是，只要把G中这条从u到v的路径中，每条权值为2w的边(a,b)上加上一个点vab后分为两条权值都为w的边，那么这条路径就成了G’中的一条从u到v的路径。并且，这两条路径有相同的权值。反之，G’中任何一条从u到v的路径也对应了G中的一条从u到v的路径，只要把新加的点去掉即可。所以，G’中的一条从u到v的最短路径也对应了G中的一条从u到v的最短路径，算法正确性得证。因为算法3部分都只需要O(m+n)时间，其复杂度满足要求。假设我们用一个有向图G(V,E)表示主要城市间的铁路网。有向边(u,v)表示从城市u到城市v之间有火車直达。又假设，不论从城市u到城市v距离多远，从u到v，火车只有两种票价，一种是慢車票，价格为c1；另一种是快車票，价格为c2(>c1)。再假设，不论从城市u到城市v距离多远，坐慢車者需要d1旅行时间而坐快車者则需d2(<d1)旅行时间。请设计一个O(m+n)算法找出一条从起点s到终点t的最佳路径使得在总的票价不超过M的条件下总的旅行时间最少。你的算法在给出路径时需要同时标明路径上那一条边坐慢車，那一条边坐快車。解： 我们注意到，一条最佳路径一定是一条边数最少的路径。假定p(s,t)是这样一条路径。那么，如何决定那一条边坐慢車，那一条边坐快車呢？因为每条边都只有相同的两种选择，我们只需决定有几条边坐快车即可。下面是伪码，正确性显然。Best-Route(G(V,E),c1,c2,d1,d2,M)callBFS(G(V,E),s)togetBFStreeTrootedatsLetp(s,t)bethepathinTfromstotk¬|p(s,t)| //边的个数h¬0 //坐快車次数whilec1´(k–h)+c2´h£M h¬h+1endwhileifh=0 thenreturn(Misnotenoughtotravel) //钱不够旅行 else hh-1 t¬d1´(k-h)+d2´h c¬c1´(k-h)+c2´hendifreturn{p(s,t),t,c,h} //沿路径p坐h次快车，其余为慢車。总价是c，总时间是tEnd(a)对下面的有向图从顶点a开始作DFS搜索并标出每个顶点u的发现时刻和完成时刻d(u)/f(u)。如遇有多种选择，用字母顺序决定。分别列出反向边集合、前向边集合、和交叉边集合中所有边。列出图中每个强连通分支中的顶点并画出分支图。解：(a)(b) 反向边集合={(c,j),(b,a),(h,s),(f,p)}。前向边集合=空集交叉边集合={(e,d),(s,g),(g,p),(h,f),(h,m),(h,g)}。各强连通分支及分支图如下：.假设我们有n个盒子，B1，B2，，Bn。盒子Bi(1in)的长、宽、高分別是Li、Wi、和Di。盒子Bi和盒子Bj如果有Li<Lj、Wi<Wj、和Di<Dj，那么称盒子Bi兼容于盒子Bj。我们希望从这n个盒子里选出一组两两兼容的盒子使得他们总的容积最大。这也就是说，使得Bi∈SLi×Wi×Di最大，这里解：我们构造一个有向图G(V,E)，其中V={B1，B2，，Bn}{s，t}。这里，顶点Bi代表盒子Bi(1£i£n)。如果Li<Lj、Wi<Wj、和Di<Dj，那么就建一条从Bi到Bj的边(Bi，Bj)并赋以权值LiWiDi。此外，从s到每个Bi加一条边(s,Bi)并赋以权值0，而从每个Bi到t加一条边(Bi,t)并赋以权值LiWiDi。显然，构造这个图的时间是O(n2)。这个图显然不含回路。图构造好之后，任何一条从s到t的路径上的顶点，除s和t外，对应了一组两两兼容的盒子。而这些盒子的总容积恰恰等于路径上所有边的权值总和。因此，找出最长的一条从s到t的路径就找到了答案。下面是伪码。Maximum-Volume(L,W,D,n,S)ConstructG(V,E)asdescribedabove //按上面所述构造一图，显然无回路Longest-Path-for-DAG(G(V,E),s) S{v|vpath(s,t),v≠sort}End因为图中最多有n(n-1)/2+2n条边，而找最长路径只需O(n+|E|)时间，算法复杂度为O(n2)。重新考虑贪心法一章中的活动选择问题。假设我们有n个活动，a1，a2，，an，申请使用大礼堂。每个活动ai(1£i£n)有一个固定的开始时间si和一个完成时间fi(0si<fi<)。我们假定任何时候大礼堂只能允许一个活动在进行。两个活动ai和aj称为兼容，如果它们对应的时间区间，[si,fi)和[sj,fj)不相交。现在我们希望从这n个活动中选出一个两两兼容的子集A使得大礼堂被使用的时间最长。注意，与贪心法一章中的活动选择问题不同的是，我们不追求集合中活动的个数最多，而是总时间最长，也就是使ai∈A(fi-si)解：Max-Utilization-Activity-Selection(S)构造一个加权的有向图G(V,E)，其中V={a1，a2，，an}{s，t}。顶点ai代表活动ai(1£i£n)。如果fi<sj，那么就建一条从ai到aj的边(ai，aj)并赋以权值fi-si。此外，从s到每个ai加一条边(s，ai)并赋以权值0，而从每个ai到t加一条边(ai，t)并赋以权值fi-si。这个图显然无回路。找出图中从s到t的最长路径P。输出路径P上除s和t以外的各顶点所对应的活动。End显然，任何一条从s到t的路径上的顶点对应一组两两兼容的活动子集，而任何一组两两兼容的活动子集也对应了一条从s到t的路径。而且，一条从s到t的路径上边的权值总和就是路径上的顶点对应的所有活动的时间总和。所以图中从s到t的最长路径对应的两两兼容的活动使用大礼堂的总时间最长。因此，算法正确。算法用在构造图上的时间和计算最长路径的时间都是O(n2)，所以算法复杂度是O(n2)。(可达性问题)假设一个有向图G=(V，E)的每个顶点uV都赋与了一个取自集合{1,2,…,|V|}的整数标号L(u)。各顶点的标号都不同。对每个顶点u，我们定义R(u)={vV|从u到v有路径}，也就是u可以到达的所有点的集合。我们再定义min(u)为R(u)中标号最小的顶点。即min(u)=v使得L(v)=min{L(w)|wR(u)}。请设计一个O(n+m)算法为每一个uV算出min(u)。这里，|V|=n，|E|=m。解：让我们定义有标号L(u)=k的顶点u为vk，k=1，2，…，n。也就是，L(v1)=1，L(v2)=2，…，L(vn)=n，算法如下，证明随后。Reachability((G(V,E))ConstructtransposegraphGT(V,ET) //构造图G的反置图foreachvV color(v)Whiteendforfork1ton ifcolor(vk)=White then DFS-visit(GT(V,ET),vk) DFS的附加操作是，为每个被首次访问的顶点u，做以下操作 min(u)vk //DFS中访问到的点u都有min(u)=vk endifendforEnd正确性证明

: 我们的思路是，第1步找出所有能够到达v1的顶点。如果点u可以到达v1，那么显然有min(u)=v1，1是最小的标号，因而min(u)就解决了。而且，从点u到v1的路径上任何一点w也必有min(w)=v1。把所有可到达v1的路径合在一起实际上是一棵以v1为根的树，树上每一点w都有min(w)=v1。不过，这棵树上的边的方向都是指向根的方向。那么，在GT中，从点v1为起始点的DFS就正好可以找到这棵树，也就是DFS树。第1步之后，如果图中还有未被DFS访问到的点，那么这些点在原图G中不可能有路径到第1步的DFS树中任何一个点。所以，我们可以在余下的顶点中重复第1步的做法。也就是在余下的顶点(白色的点)中找一个标号最小的点vk，从点vk为起始点在转置图GT中做一轮DFS就正好可以找到所有min(w)=vk的点w。显然，点vk是这些点能到达的有最小标号的点。第2步之后，如果图中还有未被DFS访问到的点，那么这些点在原图G中不可能有路径到前2步的DFS所访问过的点。我们可以在余下的顶点中重复第1步的做法，直到所有的顶点都被访问到。因为每一轮DFS都正确地为所访问的点找到可到达的最小标号，算法正确性得证。重新考虑第6章习题10。一块长方形电路板的上下两边各有n个端口并用数字从左到右顺序标为1，2，3，…，n。根据电路设计的要求，我们需要把上边的n个端口和下边的n个端口配对用导线连接。假设与上边第i个端口号连接的下边的端口号是π(i)，那么要连接的n个对子为(i,π(i))(1≤i≤n)。下面的图给出了一个n=8的例子。现在的问题是，找一组导线不相交的对子，使它含有的对子最多。比如在下图中，{(2，1)，(5，2)，(6，5)，(8，7)}就是最大的一组，它含有4个不相交的对子。请设计一个O(n2)算法把这个问题转化为一个图的问题后解出。解：我们构造一个有向图G(V,E)如下：V={s}{v1，v2，，vn}，其中vi代表线段(i,π(i))(1≤i≤n)。如果(i,π(i))和(j,π(j))(i<j)不相交，画一条从vi到vj的边。加一条从源点s到每个vi(1≤i≤n)的边。显然，这个图没有回路。容易看出，任一条从s出发的路径上的点所对应的线段都不会相交，反之，任何一组不相交的线段，按其上边端口号从小到大排序后，加上起始点s，就是一条从s开始的图G的路径。所以上面问题转化为找一条图G的最长路径问题。第8章中有现成的O(n+m)箅法。加上构图时间，算法复杂度为O(n2)。(a)有向图G=(V，E)有n个顶点，V={v1，v2，，vn}。经过DFS搜索后，每个顶点vi的发现时刻和完成时刻d(vi)/f(vi)都已标出(1£i£n)，并分别存在数组D[1..n]和F[1..n])中。现在，请设计一个O(n)时间的算法，它根据这n个区间把相应的DFS树或森林构造出来。(b) 假设某有向图有8个顶点,a，b，c，d，e，f，g，h。经过DFS搜索后，它们的发现时刻和完成时刻如下。请用问题(a)中的算法把DFS树(或森林)画出来。a(8/9)，b(13/16)，c(2/3)，d(1/12)，e(4/11)，f(5/6)，g(7/10)，h(14/15)。(c) 假定(e,g)，(b,a)，(h,c)，(a,d)，(f,c)是问题(b)中有向图的边。请指出它们分别是DFS树(或森林)里的边，还是反向边，还是前向边，还是交叉边。解:(a)DFS-Tree(D[1..n],F[1..n],V,T) //D和F分别表示发现时刻和完成时刻CountingsortD[1..n]suchthatD[1]<D[2]<…<D[n]T¬ÆStackS¬Æfori¬1ton u¬Top(S) //指针指向栈顶元素。如果S=Æ，则u=nil whileu¹nilandF[i]>F[u] then Pop(S) u¬Top(S) endwhile ifu¹nil then T¬T{(u,vi)} endif Push(S,vi)endforEnd正确性证明：因为D[1..n]和F[1..n])都是正整数并且不大于2n，所以计数排序只需O(n)时间。排序后，后面的区间对应的顶点只能是前面某个点的儿子或者是某一轮DFS树的根。因为每个顶点被压入堆栈只有一次，被弹出最多一次，所以算法有复杂度O(n)。因为区间和它对应的顶点是一一对应的，在下面讨论中，两者不作区分。在for循环中，我们用堆栈来鉴别所有的父子关系，一旦发现，就有一条树里的边。因为一开始堆栈为空，第一次for循环后，根(V[1])被压入堆栈。后面的每次循环都是在判断序列中下一个顶点的父亲是谁。我们从栈顶开始找。因为D[1]<D[2]<…<D[n]，根据区间套定理，前面的点不会是后面的点的儿子。所以如果D[u]<D[i]，但却有F[u]<F[i]，我们把u从堆栈中弹出，并且再也不需考虑u了。这是因为根据区间套定理，V[i]和V[u]的区间不相交，必有F[u]<D[i]。V[i]不可能是V[u]的儿子，而后面任一点也不可能。如果F[i]<F[u]，那么V[i]显然是u的儿子，加上一条树的边(u,V[i])。注意，V[i]不可能是更前面的点的儿子，因为V[u]的区间是最小的包含V[i]的区间。同时，我们压入V[i]，因为它可能是后面顶点的父亲。如果堆栈中所有点都被弹出，那么，V[i]自己就是某一轮DFS的根而被压入堆栈。所以上面算法正确地为每个儿子找到它的父亲，证明毕。(b) (c) 假定(e,g)，(b,a)，(h,c)，(a,d)，(f,c)是上述有向图的边。请指出它们分别是DFS树里的边，还是反向边，还是前向边，还是交叉边。(e,g)是树里的边，(b,a)，(h,c)，(f,c)是交叉边，(a,d)是反向边。假设有一个nm的棋盘。棋盘中每一格中有一个数字并各不相同。我们用数组A[i，j](1£i£n,1£j£m)存放这mn个不同数字。你可以从某一格运动到相邻的一个格子中去，如果你所在的格子中数字小于这个相邻的格子中数字。比如，在下面35的棋盘中，你可以从格子(1，1)走到格子(2，1)。连续的从一个格子到另一格子的运动形成一条路径。请设计一个O(mn)的算法找出一条最长的路径。例如，在下面35的棋盘中，最长的路径是(2，2)，(2，3)，(1，3)，(1，4)，(2，4)，(2，5)，(3，5)，(3，4)，(3，3)}。

解：我们定义L[i,j]=以格子(i,j)为终点的最长的一条路径的长度。Longest-Walk(A[1..m,1..n])fori1tom //初始化 forj1ton L[i,j]0 [i,j]nil //父亲指针 endforendforConstructadirectedgraphG(V,E),whereV={V[i,j]|1im,1jn},E={(V[i,j],V[i’,j’])|((i=i’and|j–j’|=1)or(|i-i’|=1andj=j’))andA(i,j)<A(i’,j’) //如果格子A[i,j]中的值小于相邻格子A[i’,j’]中数字时，加一条边。Topological-sort(G(V,E))LetU[1..mn]bethesequence //拓扑排序后的顶点序列fork1tomn (i,j)U[k] //U[k]对应的顶点是V[i,j] dL[i,j]+1 if(V[i,j],V[i,j-1])Eandd>L[i,j-1] then L[i,j-1]d [i,j-1](i,j) endif if(V[i,j],V[i,j+1])Eandd>L[i,j+1] then L[i,j+1]d [i,j+1](i,j) endif if(V[i,j],V[i-1,j])Eandd>L[i-1,j] then L[i-1,j]d [i-1,j](i,j) endif if(V[i,j],V[i+1,j])Eandd>L[i+1,j] then L[i+1,j]d [i+1,j](i,j) endifendforL(u,v)max{L[i,j]|1im,1jn}} //下面是从L(u,v)开始根据父亲指针往回逐步把这条最长路径找到。dL(u,v)S //清空堆栈Push(S,(u,v)) while[u,v]nil (u,v)[u,v] Push(S,(u,v))endwhileReturnS,d //堆栈中从顶到底的元素组成这条最长路径。因为图中每个点最多有4条边，所以构造这个图和做拓扑排序都只要O(mn)时间。显然这个图是没有回路的。所以，只要在这个图中找到一条最长路径即可。我们按拓扑排序后的顺序逐点访问。每访问一个点时，以这点为终点的最长路径已知。所以，在访问这点时，主要工作就是逐一检查它的邻居(最多4个)。如果从这点到某个邻居可以为这个邻居提供更长路径的话，则帮这个邻居进行更新。每个邻居都检查完之后，访问序列中下一个点。当走到下一个点(i,j)=U[k]时，所有序列中这点前面的点的最长路径都已算出，而且能到达(i,j)的点也都为(i,j)进行了更新的操作。因为到达(i,j)的任何路径必须经过前面的相邻的某个点(后向邻居)，所以当访问点(i,j)时，L[i,j]已经算出。因此，算法是正确的。因为每个点最多需要为4个邻居更新，而且更新可以在O(1)时间内完成，算法复杂度为O(mn)。给定一个无回路的有向图G(V，E)和其中两个顶点s和t，我们希望算出一共有多少条不同的从s到t的路径。我们假定任何两条路径，只要有一条边不同，就是两条不同路径。请为此设计一个O(m+n)的算法。算法只要统计出数字即可，不需要给出具体路径。解：下面是算法的伪码，其正确性显然。Path-Count(G(V，E),s,t)Topological-Sort(G(V,E),s)LetthesortedsequencebeA[1..h],whereA[1]=s //如果有s不能到达的点，h<n fori¬1toh letu=A[i] count(u)¬0 //初始化，count[u]是s到u的路径数endforcount(s)¬1 //s有一条到自己的路径fork=1toh-1 letu=A[k] foreachvÎAdj(u) count(v)¬count(v)+count(u) endforendforreturncount(t)End另一个对有向图G=(V，E)进行拓扑排序的方法是，先找一个入度为0的顶点，把它输出并把这个顶点连同从它出去的边全部从图中刪去。然后，再找一个入度为0的顶点，把它输出后，也把它连同从它出去的边全部从图中刪去。不断地这祥做下去直到每个点都被输出。请给出一个O(n+m)的算法来实现这个做法。当图G中有回路时，会有什么问题

?解: 算法如下：Alternative-Topological-Sort(G(V，E))foreachuV in-degree(u)0 //初始化，然后计算endforforeach(u,v)E in-degree(v)in-degree(v)+1//计算in-degree只需O(m)时间endforQ //清空一个队列foreachuV ifin-degree(u)=0 thenEnqueue(Q,u) //O(n)时间把所有入度为0的点入队 endifendforwhileQ uDequeue(Q) outputu //依次输出队列中入度为0的点 VV–{u} foreachvAdj(u) in-degree(v)in-degree(v)-1 //边(u,v)去掉了 ifin-degree(v)=0 thenEnqueue(Q,v) //v是新的入度为0的点 endif endfor endwhile //while循环用时O(m)ifV //检查是否有回路 thenreturn(Thereisacycle) //报告有回路endifEnd显然算法的复杂度为O(n+m)。如果有回路，算法仍可进行，但那些在回路中的点不可能入度为0。所以算法结束时，有些点未被输出。这些点是强连通分支中的点以及从某个强连通分支可以到达的点。如果一个有向图G(V，E)中任两个顶点，u，vÎV，之间有路径从u到v或从v到u，那么G称为是半连通的图(semi-connectedgraph)。请给出一个O(m+n)的算法来判断图G是否是半连通。你需要证明其正确性并分析时间复杂度。解：算法如下：Semi-connected(G(V，E))调用强连通分支算法算出连通分支C1，C2，…，Ck。构造强连通分支图GC对强连通分支图GC中点进行拓扑排序，设序列为C1，C2，…，Ck。检查从Ci到Ci+1是否有边(1£i£k-1)。如果都有,则G是半连通的，否则不是。因为每一步都可以在O(m+n)时间内完成，上面的算法是个O(m+n)算法。正确性证明如下。正确性证明：我们分两种情况分析：假设Ci到Ci+1有边(1£i£k-1)。这种情况下，如果任两顶点u和v同属一个分支，则他们之间无疑有通路。不然，设uCi和vCj，i<j，因为Ci到Ci+1有边(1£i£k-1)，所以从u到v有通路。因此，G是半连通的。假设对某个i，Ci到Ci+1没有边(1£i£k-1)。在这种情况下，Ci中的点u与Ci+1中的点v之间没有路径。由以上两点知，Ci到Ci+1有边(1£i£k-1)是半连通的充要条件，因此算法正确。一个有向图G(V，E)的子图T称为有向支撑树，如果它满足以下条件：它包括所有V中顶点；图T不含回路；图T中存在一个顶点r，称为T的根，使得从r到任何一个顶点有唯一的一条简单路径。请设计一个O(n+m)算法来判断一个给定有向图G(V,E)是否有一个有向支撑树。如果有，则找出一个有向支撑树。解: 算法如下：Directed-ST(G(V，E))用DFS(G)计算各顶点uV的发现和完成时刻d(u)/f(u);找出最后完成的顶点u，即f(u)=max{f(v)|vV};从顶点u开始再做一遍DFS(G)；如果以u为根的DFS树T包含所有V中顶点，那么回答Yes并输出T，否则回答No；End算法复杂度显然是O(n+m)。下面证明其正确性。算法第4步中，如果以u为根的DFS树T包含所有V中顶点，显然这就是一个以u为根的有向支撑树。所以我们只需证明，如果第4步中，以u为根的DFS树T不包含所有V中顶点，那么G不存在有向支撑树。为了用反证法证明，让我们假设以u为根的DFS树T不包含所有V中顶点，但是有一个有向支撑树T*。假设T*的根是顶点r。因为以u为根的DFS树T不包含所有顶点，那么集合V’=V–T非空而且没有从T中点到V’中点的边。所以，有向支撑树T*的根r必定在V’中。因为没有从T中点到V’中点的边，也就没有从点u到点r的路径，所以点u和点r必属于不同的强连通分支。因为顶点r是有向支撑树T*的根，所以，在图G的分支图中必有一条从点r所在的分支到其它任何分支的路径，包括点u所在分支。根据书中对强连通分支算法的证明，在所有分支包含的顶点中，也就是集合V的所有顶点中，算法第一步的DFS完成后，有最大完成时刻的点必定在顶点r所在的分支中。这与f(u)最大矛盾。所以，图G不存在有向支撑树。这就证明了算法的正确性。一个图G=(V，E)的顶点子集V’ÍV称为一个独立集(independentset)，如果E中任何一条边只与V’中最多一个点有关联。这也就是说，如果V’中任意两点之间没有边，那么它就是一个独立集。最大独立集问题就是要找出图G的一个含顶点最多的独立集。如果G可以是任意一个图，那么这是一个NP-难问题。但是，如果G是一棵树T，那么，这个问题可以在O(n)时间内解决。请设计一个这样的算法。解：我们先介绍一个贪心法，然后介绍如何用DFS实现。我们注意到，一个叶子的顶点一定可以选进最大独立集，理由见下图。假设图中顶点v是叶子，它联到顶点u。如果最佳解中不含v，那么必含u，否则不可能是最大独立集。但是，如果它含有u，那么把u换成v后仍然是一个最大独立集。所以，把叶子顶点v选入最大独立集不会错。把叶子v选入最大独立集之后，u就不可以选了，所以必须把u及与之相关联的边全删除。然后，问题变为在剩下图中找出最大独立集。于是，我们可以重复以上做法。这个贪心法可以用以下DFS算法实现。假定T(V，E)是一棵树。我们用红色表示被选入独立集中的点，而蓝色表示要刪除的点。规则如下：如果一个点没有儿子，则给予红色(选中)。如果一个点有一个红色儿子，则给予蓝色(刪除)。如果一个点的所有儿子都是蓝色，则给予红色(选中)。规则的正确性显然。在下面的伪码中，我们给每个点一个变量，report，记录是否有儿子是红色。一开始，它的值是no。一旦有儿子变红色，更改为yes。Independent-Set(T(V，E)，s) //s可取任一点foreachuÎV //初始化每个点，不需要白、灰、黑颜色 p(u)¬nil report(u)¬noendforS¬ //清空堆栈Push(S,s)whileS¹ uTop(S) //不是弹出，而是建立指针 vu’snextneighborinAdj(u) //u的邻接表中下一个邻居v ifv=nil //u的邻居已全部访问完毕 then Pop(S) ifreport(u)=no then color(u)¬Red ifp(u)nil thenreport(p(u))¬yes endif else color(u)¬Blue endif else (v)u //u是v的父亲 Push(S,v) //将v压栈使得下一步访问v的邻居 endifendwhilereturn{allRedvertices} //输出所有红色的顶点End因为树中边的个数是n-1，所以算法复杂度是O(n)。一个图G=(V，E)的顶点子集V’ÍV称为一个顶点复盖(vertexcover)，如果E中任何一条边都与V’中一个或两个点有关联。最小顶点复盖问题就是要找出图G的一个有最少顶点的顶点复盖。如果G可以是任意一个图，那么这是一个NP-难问题。但是，如果G是一个树T，那么，这个问题可以在O(n)时间内解决。请设计一个这样的算法。解：因为图中一个独立集的补集是一个顶点复盖，反之亦然。所以，找到了图中的一个最大独立集，取其补集就是本题的解。因此，用与上一题同样的算法。在算法结束后，所有蓝色的顶点组成一个最小顶点复盖。下面图中的树是对某个图G=(V，E)进行双连通分支算法后得到的DFS树。每个顶点u的发现时刻d(u)和变量back(u)的值都标在图上。请根据这个图回答下面问题。指出所有的断点。列出所有双连通分支及各分支中的顶点。 ababcdefghijklmnopq(1/1)(2/1)(3/1)(4/2)(6/6)(7/6)(8/6)(9/6)(11/1)(12/1)(13/12)(14/12)(15/13)(16/13)(17/13)(10/1)(18/1)(19/1)rs(5/5)解：(a)他们是h，i，d，a，f，c。(b) C1={h,n},C2={i,o,q,s},C3={i,d},C4={a,b,d,h,e,j},C5={f,l,p,r},C6={c,f,k},C7={a,c,g,m}。如果删去连通图G(V，E)中的一条边(u，v)后图不连通，那么这条边称为一个桥(bridge)。例如下面图中的边(u，v)就是一个桥。请设计一个O(n+m)的算法找出图中所有桥。解：算法如下，正确性显然。Bridge(G(V,E))BSelectvertexs //任选一点sBi-Component-Component(G(V,E),s) //调用双连通分支算法LetthecomponentsbeC1，C2，…，Ck //设分解为k个分支fori1tok if|Ci|=1 //只含一条边的双连通分支就是一个桥 thenBBCi endif endfor returnB End假设S是有向图G(V,E)中边的一个子集，SE，并且S中的边不形成任何回路。图G(V,E)称为是“相对于集合S的无回路图”，如果图G(V,E)中任何一个回路都不经过S中的边。请设计一个O(n+m)的算法以判断图G(V,E)是不是相对集合S的无回路图。解：算法如下，证明随后。 Acyclic-with-Respect-to-S(G(V,E),S)callStrongly-Connected-Component(G(V,E))LetC[1],C[2],…,C[k]bethestrongly-connected-componentsofG(V,E)fori1tok foreachvertexvC[i] component(v)i //赋与每个顶点它的分支号 endforendforforeachedge(u,v)S ifcomponent(u)=component(v) then returnno endifendforreturnyesEnd上面的算法显然正确，因为任何一个回路必定存在于某个强连通分支内，而强连通分支内的任一条边必会被某个回路通过。算法的时间复杂度可分析如下。第3行的循环是给每个顶点打上它所在的分支号，执行n次，总共只需O(n)时间。第8行的循环检查集合S中每条边是否在某个强连通分支内，总共只需O(|S|)=O(m)时间。因为强连通分支算法需要O(n+m)时间，所以该算法复杂度为O(n+m)。在一个nn的棋盘上，有些方格标记为已占用，其余为可用。下面给出了一个88的棋盘例子。我们用(i,j)表示位于第i行第j列的方格(1≤i,j≤n)。我们用B[i,j]=0表示方格(i,j)已占用，B[i,j]=1表示方格(i,j)可以用。我们还假设方格(1,1)和(1,n)可以用。请设计一个O(n2)的算法找出从方格(1,1)到(1,n)的一条最短路径。我们假设路径中每一步必须从当前的方格进入到相邻的一个可用的方格，而不可以进入到已占用的方格。路径的长度是该路径所经过的方格的个数，包括(1,1)和(1,n)。如果不存在从(1,1)到(1,n)的路径，输出d=∞。下面图例显示了所给88棋盘中从(1,1)到(1,8)的一条最短路径，其长度是22。11标记为已占用123456782348657解: 我们用广度优先搜索来解。伪码如下，正确性显然。Shortest-Path-in-Chessboard(B[1..n,1..n])fori1ton forj1ton color(i,j)White d(i,j)∞ //从(1,1)到(i,j)的最短路径，初始长度为无穷大 π(i,j)nil endforendforQ //清空队列Qcolor(1,1)Greyd(1,1)1Enqueue(Q,(1,1))whileQ≠andcolor(1,n)=White (u,v)Dequeue(Q) //队列首项对应的方格 ifu–11andcolor(u-1,v)=WhiteandB[u-1,v]=1 //(u-1,v)在棋盘内且可用 then color(u-1,v)=Grey π(u-1,v)(u,v) d(u-1,v)d(u,v)+1 Enqueue(Q,(u-1,v)) endif ifu+1nandcolor(u+1,v)=WhiteandB[u+1,v]=1 then color(u+1,v)=Grey π(u+1,v)(u,v) d(u+1,v)d(u,v)+1 Enqueue(Q,(u+1,v)) endif ifv–11andcolor(u,v-1)=WhiteandB[u,v-1]=1 then color(u,v-1)=Grey π(u,v-1)(u,v) d(u,v-1)d(u,v)+1 Enqueue(Q,(u,v-1)) endif ifv+1nandcolor(u,v+1)=WhiteandB[u,v+1]=1 then color(u,v+1)=Grey π(u,v+1)(u,v) d(u,v+1)d(u,v)+1 Enqueue(Q,(u,v+1) endifendwhileifcolor(1,n)=White thenreturnd=∞ else StackS //准备输出路径 (u,v)(1,n) while (u,v)≠nil Push(S,(u,v)) (u,v)π(u,v) endwhileendifEnd如果d≠∞，那么堆栈S中从顶到底的元素就是一条最短路径，其长度是d(1,n)。如下图所示，在一个mn的棋盘上，有些方格标记为已占用，其余为可用。我们用(i,j)表示位于第i行第j列的方格(1≤i≤m，1≤j≤n)。我们用B[i,j]=0表示方格(i,j)已占用，B[i,j]=1表示方格(i,j)可以用。从一个可用方格可以走到同一行或同一列的相邻的可用方格，但任何时候不可以进入到已占用的方格。如果从一个可用方格可连续地走到另一个可用方格，则称这两个可用方格是连通的。请设计一个O(mn)的算法找出最大的一个互相连通的可用方格的集合。例如，在下图中，集合S={(2，4)，(3，3)，(3，4)，(4，2)，(4，3)，(4，4)}就是该图中最大的一个互相连通的可用方格的集合。111234823413657可用方格891112567解: 为方便起见，我们先用BFS设计一个子程序Connected-Squares。它为一个给定的可用方格(i,j)，找出最大的与之连通的可用方格的集合S(i,j)。那么，最大的S(i,j)(1≤i≤m，1≤j≤n)就是本题的解。Connected-Squares(i,j,S(i,j),K(i,j)) //输入B[i,j]=1，返回S(i,j)，K(i,j)=|S(i,j)|Q //队列Q初始化为空Mark(i,j)true //表示(i,j)已被访问过了S{(i,j)} //方格(i,j)是集合S(i,j)中第一个可用方格k1 //当前集合S(i,j)只有一个元素Enqueue(Q,(i,j))whileQ≠ (u,v)De-queue(Q) ifu–11andB[u-1,v]=1andMark(u-1,v)=false then Mark(u-1,v)=true SS{(u-1,v)} kk+1 Enqueue(Q,(u-1,v)) endif ifu+1mandB[u+1,v]=1andMark(u+1,v)=false then Mark(u+1,v)=true SS{(u+1,v)} kk+1 Enqueue(Q,(u+1,v)) endif ifv–11andB[u,v-1]=1andMark(u,v-1)=false then Mark(u,v-1)=true SS{(u,v-1)} kk+1 Enqueue(Q,(u,v-1)) endif ifv+1nandB[u,v+1]=1andMark(u,v+1)=false then Mark(u,v+1)=true SS{(u,v+1)} kk+1 Enqueue(Q,(u,v+1)) endifEndwhileS(i,j)SK(i,j)kreturenS(i,j),K(i,j)End下面是主程序。Largest-Set-of-Connected-Squares(B[1..m,1..n],H,h) //输出最大连通可用方格的集合H,|H|=hfori1tom forj1ton Mark(i,j)false //初始化，标记方格还没有被访问 endforendforHh0fori1tom forj1ton ifB[i,j]=1andMark(i,j)=false Connected-Squares(i,j,S(i,j),K(i,j)) //调用子程序 ifK(i,j)>h then HS(i,j) hK(i,j) endif endif endforendforReturnH,hEnd算法的正确性显然。其时间复杂度分析如下。因为每个方格被初始化一次，被检查一次，从该点去调用子程序最多一次，其结果用来更新H和h一次，所以主程序需要O(mn)时间。又因为，每个方格被标记最多一次，入队一次，出队一次，和访问4个邻居各一次，所以，子程序需要的总时间是O(mn)时间。算法符合题目要求。假设一个新兴城市划分为nn个正方形的小区。下图是一个n=8的例子。我们用(i,j)表示位于第i行第j列的小区(1≤i,j≤n)。用B[i,j]=0表示小区(i,j)里没有学校，B[i,j]=1表示小区(i,j)有学校。从一个小区到同一行或同一列的相邻的小区有路相连。请设计一个O(n2)的算法，为每一个小区(i,j)(1≤i,j≤n)，计算出到最近的有学校的小区的距离d(i,j)。这里，距离d(i,j)定义为需要经过的小区个数。如果B[i,j]=1，那么小区(i,j)本身有学校，所以d(i,j)=0。请参考下图中更多例子。2213着色的方格表示B[i,j]=1，即小区(i,j)