算法导论-复习笔记

算法导论复习笔记Chapter 22 基本图算法22.1-1 有向图邻接链表，计算节点出度和入度的时间复杂度？O(V+E)开一个degree数组，大小为结点个数，复杂度O(V);遍历邻接链表，经过边uv时，计算出度degreeu+=1,计算入度degreev+=1,复杂度O(E)22.1-4 将一个多图变成等价无向图，用邻接链表表示，时间复杂度O(V+E)多图是允许重复边和自循环边的图。开一个bool数组mark,大小为节点个数，初始化为false。复杂度O(V)。对每个顶点u的邻接链表，遍历，令v为u的边所指向的顶点；如果markv=false，将uv加入新图，并将markv设置为true；否则就跳过。复杂度O(E)再次遍历u的连边，将markv初始化整体复杂度O(V+E)伪代码:SOLVE(G,G)1 for each vetex uG2 for each v G.Adju3 if markv=false4 markv=true5 Addedge(G,u,v)6 for each vG.Adju7 markv=false22.1-6 图G的邻接矩阵表示，给出一个O(V)的算法来判断有向图G中是否存在一个通用汇点。通用汇点指的是入度|V|-1，但出度为0。等价问题：给定有向图G的VV邻接矩阵G，在O(V)时间内判断是否存在一个数k，使得对所有的i有Aik=1,对所有的j有Akj=0,(ik,jk)令i和j初值为1，若Gij=0,说明i到j无边，j不可能是通用汇点，令j=j+1;若Gij=1,说明i到j有边，i不可能是通用汇点，令i=i+1，循环直到i|V|或者j|V|;若i|V|，则不存在通用汇点，若j|V|，则检查顶点i是否满足要求。伪代码：判断是否存在通用汇点 O(V)HAS_UNIVERSL_SINK(G)1 i=j=12 while iV and jV3 if Gij=14 i=i+15 else j=j+16 if iV7 return false8 else return CHECK(G,i)CHECK(G,u)1 for each vertex vG.V2 if Guv=13 return false4 for each vertex v G.V5 if Gvu=0& u!=v6 return false7 return true检查点u是否是通用汇点【宽度优先搜索】22.2-2 计算无向图BFS后的d值和值简单，注意初始节点u的值写NIL或者写-1rstuvwxyD值43105211值swuNILrtuu22.2-4 输入如果是邻接矩阵表示的，BFS的运行时间？O(V2)对于队列中的每一个节点，都要遍历所有的节点来判断是否有边。22.2-6 举例说明一个有向图G中可能存在这样一个边集E：s到v的唯一简单路径也是一条最短路径，但是无论如何该边集E都不能通过在图G上运行BFS获得。V=1,2,3,4,5, E=(1,2),(2,3),(1,4),(4,5),(2,5),(3,4), E=(1,2),(2,3),(1,4),(4,5), s=122.2-8 求一棵树T=(V,E)的直径，并分析算法的运行时间。直径指的是树中所有最短路径的最大值。两遍BFS就能解决.设v任意一点，BFS(v)，令u=v能到达的最远点。再BFS(u)，取w为u能达到的最远点，则u和w之间的最短路径就是直径。时间复杂度是O(V+E)。注意本题的证明。反证法，设t1到t2是直径，u是v能达到的最远点，但是u不是t1或者t2中的一个，产生矛盾的结论。【深度优先搜索】22.3-2 给出DFS每个结点的发现时间和完成时间，并给出每条边的分类qrstuvwxyzdis/fin1/1617/202/78/1518/193/64/59/1213/1410/11qssvvwwsqwqttxxzzxtyyqryuyru树边树边树边后向边前向边树边树边树边后向边树边后向边横向边横向边树边22.3-7 用栈实现DFS，写出伪代码DFS-VISIT(G,u)1 STACK.PUSH(u)2 while(! STACK.empty)3 u=STACK.top4 if u.color=GRAY5 u.color=BLACK6 time=time+17 u.f=time8 STACK.POP9 continue10if u.color=WHITE11u.color=GRAY12time=time+113u.d=time14for each vG:Adju15if v.color=WHITE16v.=u17STACK.PUSH(v)22.3-8 举出一个反例反驳：有向图G包含u到v的路径，并且DFS时u.dw-v，且du若强连通有向图G有欧拉回路，则可知对于出发点s，假设有x次从s出，则最后回到s必须恰好有x次，因此对于s，出度和入度必然相等。假设对于某个非出发点v，出度与入度不相等；假设出度y大于入度x，则第x次从v离开后再也不能回到v，剩余的y-x条边不能被访问到；假设出度y小于入度x，则第y+1次进入v后无法出去。由此可知，对于非出发点v，入度与出度同样相等。因此G有Euler回路则入度等于出度成立。v1-v2-vi的路径，其中vi不等于s，则遍历过程中进入vi的次数比从vi走出的次数多一次，这样就肯定有一条从vi出去的边没有被访问到。所以不成立。这样遍历一次后会形成一个子回路，再在这个子回路上某个不同于s点的s1点继续遍历，会形成一个以s1为起始点（也是终止点）的子回路，这两个回路没有公共边，而这两个子回路明显可以合并为一个回路，该回路为s-e-s1-f-s1-s, 这样不断扩展就必然形成一个欧拉回路。b. 从任意点开始DFS并在DFS过程中保存回路上的边。DFS的复杂度是O(E)的。23.1-5 设e为连通图G的某条环路上权重最大的边，证明：图G=(V,E-e)中存在一棵最小生成树，它也同时是G的最小生成树。也就是说，G中存在一棵不包含边e的最小生成树。证明：反证。假设G中所有最小生成树都包含e。任取一个这样的最小生成树T，在T上去掉e，将T分为两棵子树T1和T2，T1上顶点集合为V1，T2上顶点集合为V2，则(V1,V2)是一个割。e所在的圈至少穿越割(V1,V2)两次，C至少有2条边在(V1,V2)中，其中一条边是e。令e为除了e之外的另外一条边，则w(e)w(e)。将e并到T1和T2上，将T1和T2连接成一棵新的生成树T。由于T是在T上去掉e、加入e后形成的，因此w(T)w(T)。因此,T也是G的一棵最小生成树，且T中不包含e，与假设矛盾。23-4 第三种最小生成树算法。c. MayBE-MST-C(G,w)1 T=空集2 for each edge e, taken in arbitrary order3 T=Te4 if T has a cycle c5 let e be maximum-weight edge on c6 T=T-e7 return T证明：算法实际上是在图G中删除一些圈上权值最重的边，最后得到一棵MST。设删除的边依次是e1,e2,em-n+1,剩余的图一次是G0,G1,.,Gm-n+1，其中G=G0,Gm-n+1=T, m=|E|，n=|V|。证明Gi+1的MST同时也是Gi的MST即可。前面23.1-5已经证明存在Gi+1的MST T同时也是Gi的MST，而Gi+1的所有MST的大小与T一样，所以它们都与Gi的MST大小一样，所以它们都是Gi的MST。从而Gm-n+1必然是Gm-n,G0的MST。23-1 次优最小生成树每次从最小生成树里换掉一条边，用不在最小生成树中的一边代替。23-3 瓶颈生成树最小生成树是瓶颈生成树。24.1-6 假定G为一个带权重的有向图，并且图中存在一个权重为负值的环路。给出一个有效算法列出所有属于该环路上的结