算法导论-复习笔记.doc

.算法导论复习笔记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=true