《算法导论》复习笔记
Chapter22基本图算法
有向图邻接链表，计算节点出度和入度的時间复杂度
O(V+E)
开一种degree[]数组，大小為結点个数，复杂度O(V);
遍历邻接链表，通过边uv時，计算出度degree[u]+=1,计算入度degree[v]+=1,复杂度O(E)
将一种多图变成等价无向图，用邻接链表表达，時间复杂度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∈G
2 foreachv∈[u]
3 ifmark[v]==false
4 mark[v]==true
5 Addedge(G’,u,v)
6 foreachv∈[u]
7 mark[v]=false
图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=1
2whilei≤Vandj≤V
3 ifG[i][j]==1
4 i=i+1
5 elsej=j+1
6ifiV
7 returnfalse
8elsereturnCHECK(G,i)
CHECK(G,u)
1foreachvertexv∈
2 ifG[u][v]=1
3 returnfalse
4foreachvertexv∈
5 ifG[v][u]==0u!=v
6 returnfalse
7returntrue
检查点u与否是通用汇点
【宽度优先搜索】
计算无向图BFS后的d值和π值
简朴，注意初始节点u的π值写NIL或者写-1
r
s
t
u
v
w
x
y
D值
4
3
1
0
5
2
1
1
π值
s
w
u
NIL
r
t
u
u
输入假如是邻接矩阵表达的，BFS的运行時间
O(V^2)
对于队列中的每一种节点，都要遍历所有的节点来判断与否有边。
举例阐明一种有向图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=1
求一棵树T=(V,E)的直径，并分析算法的运行時间。
直径指的是树中所有最短途径的最大值。
两遍BFS就能处理.
设v任意一点，BFS(v)，令u=v能抵达的最远点。再BFS(u)，取w為u能到达的最远点，则u和w之间的最短途径就是直径。時间复杂度是O(V+E)。
注意本題的证明。反证法，设t1到t2是直径，u是v能到达的最远点，不过u不是t1或者t2中的一种，产生矛盾的結论。
【深度优先搜索】
給出DFS每个結点的发現時间和完毕時间，并給出每条边的分类
q
r
s
t
u
v
w
x
y
z
dis/fin
1/16
17/20
2/7
8/15
18/19
3/6
4/5
9/12
13/14
10/11
qs
sv
vw
ws
qw
qt
tx
xz
zx
ty
yq
ry
uy
ru
树边
树边
树边
后向边
前向边
树边
树边
树边
后向边
树边
后向边
横向边
横向边
树边
用栈实現DFS，写出伪代码
DFS-VISIT(G,u)
1(u)
2while(!
3 u=
4 if==GRAY
5 ==BLACK
6 time=time+1
7 =time
8
9 continue
10 if==WHITE
11 =GRAY
12 time=time+1
13 =