算法导论-复习笔记

1、算法导论复习笔记Chapter22基本图算法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加入新图，

2、并将 markv 设置为 true ；否则就跳过。复杂度 O(E)再次遍历 u 的连边，将 markv 初始化整体复杂度 O(V+E)伪代码 :SOLVE( G,G )1 for each vetex u G2for each v G.Adju3if markv=false4markv=true5Addedge(G ,u,v)6for each v G.Adju7markv=false22.1-6图 G 的邻接矩阵表示，给出一个O(V) 的算法来判断有向图G 中是否存在一个通用汇点。通用汇点指的是入度|V|-1 ，但出度为0。等价问题：给定有向图G 的 VV 邻接矩阵 G，在 O(V) 时间内

3、判断是否存在一个数k ，使得对所有的 i 有 Aik=1,对所有的 j 有 Akj=0,(ik,j k)令 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)i=j=1while i V and j Vif Gij=14i=i+1else j=j+1if iVretur

4、n falseelse return CHECK(G,i)CHECK(G,u)1 for each vertex v G.V2if Guv=13return false4 for each vertex v G.V5ifGvu=0& u!=v6return false7 return true检查点 u 是否是通用汇点【宽度优先搜索】22.2-2计算无向图BFS 后的 d 值和 值简单，注意初始节点u 的值写 NIL 或者写 -1rstuvwxyD 值43105211值swuNILrtuu22.2-4输入如果是邻接矩阵表示的，BFS 的运行时间？O(V2)对于队列中的每一个节点，都要遍历所有的

5、节点来判断是否有边。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之间

6、的最短路径就是直径。时间复杂度是O(V+E)。注意本题的证明。反证法，设t1到t2是直径，u是v 能达到的最远点，但是u 不是t1或者t2中的一个，产生矛盾的结论。【深度优先搜索】22.3-2给出 DFS 每个结点的发现时间和完成时间，并给出每条边的分类dis/finq1/16r17/20s2/7t8/15u18/19v3/6w4/5x9/12y13/14z10/11qssvvwwsqwqttxxzzxtyyqryuyru树边树边树边后向前向树边树边树边后向树边后向横横树边边边边向向边边边22.3-7用栈实现 DFS ，写出伪代码DFS-VISIT(G,u)STACK.PUSH(u)while

7、(! STACK.empty)u=STACK.topif u.color=GRAY5u.color=BLACK6time=time+17u.f=time8STACK.POP9continue10if u.color=WHITE11u.color=GRAY12time=time+113u.d=time14for each v G:Adju15if v.color=WHITE16v.=u17STACK.PUSH(v)22.3-8 举出一个反例反驳：有向图G 包含 u 到 v 的路径，并且 DFS 时 u.dw-v，且 du 若强连通有向图G 有欧拉回路，则可知对于出发点s，假设有 x 次从 s 出

8、，则最后回到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 点继

9、续遍历，会形成一个以s1 为起始点（也是终止点）的子回路，这两个回路没有公共边，而这两个子回路明显可以合并为一个回路，该回路为s- -e-s1-f-s1- -s, 这样不断扩展就必然形成一个欧拉回路。从任意点开始 DFS 并在 DFS 过程中保存回路上的边。DFS 的复杂度是 O(E) 的。23.1-5设 e 为连通图小生成树，它也同时是G 的某条环路上权重最大的边，证明：图G =(V,E-e) 中存在一棵最G 的最小生成树。也就是说，G 中存在一棵不包含边e 的最小生成树。证明：反证。假设G 中所有最小生成树都包含e 。任取一个这样的最小生成树T，在 T 上去掉 e ，将T 分为两棵子树T1

10、 和 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 第三种最小生成树算法。MayBE-MST-C(G,w) 1T= 空集2for each edge e,taken in arbitrar

11、y orderT=T eif T has a cycle c5let e be maximum-weight edge on c6T=T-e 7 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 的 MSTT 同时也是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 为一个带权重的有向图，并且图中存在一个权重为负值的环路。给出一个有效算法列出所有属于该环路上的结点。证明正确