@zqbinggong
2018-03-19T23:00:16.000000Z
字数 2414
阅读 895
广度优先搜索
深度优先搜索
拓扑排序
强连通分量
算法导论
BFS(G,s)————
for each vertex u in G.V -{s}
u.color = white
u.d = 00 #s到u的距离
u.p = nil #u的前驱
s.color = gray
s.d = 0
s.p = nil
Q = empty queue
enqueue(Q,s)
while Q is not empty
u = dequeue(Q)
for each v in G.adj[u]
if v.color == white
v.color = gray
v.d = u.d + 1
v.p = u
enqueue(Q,v)
u.color = black
DFS(G)
for each vertex u in G.V
u.color = white
u.p = nil
time = 0
for each u in G.V
if u.color == white
DFT-visit(G,u)
DFT-visit(G,u)
time = time + 1
u.d = time
u.color = gray
for each v in G.adj[u]
if v.color == white
v.p = u
DFT-visit(G,v)
u.color = black
time = time + 1
u.f = time
边的分类
DFS会产生对边进行分类的信息,对于边(u,v)
对于无向图G,在对无向图进行深度优先搜索中,从来不会出现前向边和横向边。启发式证明,至所以有向图会出现这两种边,在于边是有方向的,从u不能到v但反之可以,从而使得从v探索到u时,u已经被发现
topological-sort(G)
call dfs(G) to compite finishing time v.f for each vertex v
as each vertex is finished, insert in onto the front of the linked list
return the linked list
strongly-connected-components(G)
call dfs(G) to compute finishing time u.f for each vertex u
compute G.transvertion
call dfs(G^T), but in the main loop of dfs,consider the
vertices in order of decreasing u.f
output the vertices of each tree in the df forest formed in the
second call of dfs as a seperate strongly connected component