资源描述：
《算法导论-复习笔记》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《算法导论》复习笔记Chapter22基本图算法22.1-1有向图邻接链表，计算节点出度和入度的时间复杂度？O(V+E)开一个degree[]数组，大小为结点个数，复杂度O(V);遍历邻接链表，经过边uv时，计算出度degree[u]+=1,计算入度degree[v]+=1,复杂度O(E)22.1-4将一个多图变成等价无向图，用邻接链表表示，时间复杂度O(V+E)多图是允许重复边和自循环边的图。开一个bool数组mark[],大小为节点个数，初始化为false。复杂度O(V)。对每个顶点u的邻接链表，遍历，令v为u的边所指向的顶点；如果mark[v]=false，将uv加入新图，并将mar
2、k[v]设置为true；否则就跳过。复杂度O(E)再次遍历u的连边，将mark[v]初始化整体复杂度O(V+E)伪代码:SOLVE(G,G’)1foreachvetexu∈G2foreachv∈G.Adj[u]3ifmark[v]==false4mark[v]==true5Addedge(G’,u,v)6foreachv∈G.Adj[u]7mark[v]=false22.1-6图G的邻接矩阵表示，给出一个O(V)的算法来判断有向图G中是否存在一个通用汇点。通用汇点指的是入度
3、V
4、-1，但出度为0。等价问题：给定有向图G的V×V邻接矩阵G，在O(V)时间内判断是否存在一个数k，使得对所有的i
5、有A[i][k]=1,对所有的j有A[k][j]=0,(i≠k,j≠k)令i和j初值为1，若G[i][j]=0,说明i到j无边，j不可能是通用汇点，令j=j+1;若G[i][j]=1,说明i到j有边，i不可能是通用汇点，令i=i+1，循环直到i>
6、V
7、或者j>
8、V
9、;若i>
10、V
11、，则不存在通用汇点，若j>
12、V
13、，则检查顶点i是否满足要求。伪代码：判断是否存在通用汇点O(V)HAS_UNIVERSL_SINK(G)1i=j=12whilei≤Vandj≤V3ifG[i][j]==14i=i+15elsej=j+16ifi>V7returnfalse8elsereturnCHECK(G,i)C
14、HECK(G,u)1foreachvertexv∈G.V2ifG[u][v]=13returnfalse4foreachvertexv∈G.V5ifG[v][u]==0&u!=v6returnfalse7returntrue检查点u是否是通用汇点【宽度优先搜索】22.2-2计算无向图BFS后的d值和π值简单，注意初始节点u的π值写NIL或者写-1rstuvwxyD值43105211π值swuNILrtuu22.2-4输入如果是邻接矩阵表示的，BFS的运行时间？O(V^2)对于队列中的每一个节点，都要遍历所有的节点来判断是否有边。22.2-6举例说明一个有向图G中可能存在这样一个边集Eπ：s
15、到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能达到的最远
16、点，但是u不是t1或者t2中的一个，产生矛盾的结论。【深度优先搜索】22.3-2给出DFS每个结点的发现时间和完成时间，并给出每条边的分类qrstuvwxyzdis/fi1/1617/202/78/1518/193/64/59/1213/1410/11nqssvvwwsqwqttxxzzxtyyqryuyru树边树边树边后向前向树边树边树边后向树边后向横横树边边边边向向边边边22.3-7用栈实现DFS，写出伪代码DFS-VISIT(G,u)1STACK.PUSH(u)2while(!STACK.empty)3u=STACK.top4ifu.color==GRAY5u.color==BLAC
17、K6time=time+17u.f=time8STACK.POP9continue10ifu.color==WHITE11u.color=GRAY12time=time+113u.d=time14foreachv∈G:Adj[u]15ifv.color==WHITE16v.π=u17STACK.PUSH(v)22.3-8举出一个反例反驳：有向图G包含u到v的路径，并且DFS时u.d
