《算法导论-复习笔记》由会员分享，可在线阅读，更多相关《算法导论-复习笔记（8页珍藏版）》请在金锄头文库上搜索。
1、算法导论复习笔记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，将 u
2、v加入新图，并将 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(
3、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
4、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
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(
6、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 用栈实现 D
7、FS，写出伪代码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 的路径，并且 DF
8、S 时 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 走出的次数多一次，
9、这样就肯定有一条从 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 中存在一棵不
10、包含边 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
11、，与假设矛盾。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 同时也是
12、 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 为一个带权重的有向图，并且图中存在一个权重为负值的环路。给出一个有效算法列出所有属于该环路上的结点。证明正确性。对 G 进行改造，增加一个新的顶点 s，以及 s 到 G 中所有顶点的边。边上的权重均为 0.记为G=(V,E)。将 E 中的边任意定一个顺序。对 E 中每一条边 e，将 e 从 G上去掉，调用 Bellmanford 算法测试当前图上是否有负圈。若有，将 e 永久删除。否则，表明 e 在剩下的唯一一个负圈中，将 e 放回 G。测试完 E 中所有的边之后，最后留在 G中的就是负圈。
