算法导论-深刻复习记录文本.doc

《算法导论》-1有向图邻接链表,计算节点出度和入度的时间复杂度?O(V+E)开一个degree[]数组,大小为结点个数,复杂度O(V);遍历邻接链表,经过边uv时,计算出度degree[u]+=1,计算入度degree[v]+=1,复杂度O(E)-4将一个多图变成等价无向图,用邻接链表表示,时间复杂度O(V+E)多图是允许重复边和自循环边的图。开一个bool数组mark[],大小为节点个数,初始化为false。复杂度O(V)。对每个顶点u的邻接链表,遍历,令v为u的边所指向的顶点;如果mark[v]=false,将uv加入新图,并将mark[v]设置为true;否则就跳过。复杂度O(E)再次遍历u的连边,将mark[v]初始化整体复杂度O(V+E)伪代码:SOLVE(G,G’)1foreachvetexu∈G2 foreachv∈[u]3 ifmark[v]==false4 mark[v]==true5 Addedge(G’,u,v)6 foreachv∈[u]7 mark[v]=-6图G的邻接矩阵表示,给出一个O(V)的算法来判断有向图G中是否存在一个通用汇点。通用汇点指的是入度|V|-1,但出度为0。等价问题:给定有向图G的V×V邻接矩阵G,在O(V)时间内判断是否存在一个数k,使得对所有的i有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>|V|或者j>|V|;若i>|V|,则不存在通用汇点,若j>|V|,则检查顶点i是否满足要求。伪代码:判断是否存在通用汇点O(V)HAS_UNIVERSL_SINK(G)1i=j=12whilei≤Vandj≤V3 ifG[i][j]==14 i=i+15 elsej=j+16ifi>V7 returnfalse8elsereturnCHECK(G,i)CHECK(G,u)1foreachvertexv∈ ifG[u][v]=13 returnfalse4foreachvertexv∈ ifG[v][u]==0&u!=v6 returnfalse7returntrue检查点u是否是通用汇点【宽度优先搜索】-2计算无向图BFS后的d值和π值简单,注意初始节点u的π值写NIL或者写--4输入如果是邻接矩阵表示的,BFS的运行时间?O(V^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=-8求一棵树T=(V,E)的直径,并分析算法的运行时间。直径指的是树中所有最短路径的最大值。,BFS(v),令u=v能到达的最远点。再BFS(u),取w为u能达到的最远点,则u和w之间的最短路径就是直径。时间复杂度是O(V+E)。注意本题的证明。反证法,设t1到t2是直径,u是v能达到的最远点,但是u不是t1或者t2中的一个,产生矛盾的结论。【深度优先搜索】-2给出DFS每个结点的发现时间和完成时间,并给出每条边的分类qrstuvwxyzdis/fin1/1617/202/78/1518/193/64/59/1213/1410/-7用栈实现DFS,写出伪代码DFS-VISIT(G,u)(u)2while(!)3 u= ==GRAY5 ==BLACK6 time=time+17 =time8 continue10 ==WHITE11 =GRAY12 time=time+113 =time14 foreachv∈G:Adj[u]15 ==WHITE16 =u17 (v)-8举出一个反例反驳:有向图G包含u到v的路径,