图的搜索算法.ppt

文档介绍：图的搜索算法
第1页，共39页，编辑于2022年，星期五
图的邻接表表示
对图（有向或无向）G=<V, E>（为方便记，假定V={1, 2, …, n}），其邻接表表示是一个由|V|个链表组成数组，对每个u  V，链表Adj for each vertex s V[G]
7 do if color[s] = WHITE
8 then color[s] ← GRAY
9 d[s] ← time← time +1
10 PUSH(S, s)
11 while S≠
12 do u←TOP(S)
13 if v Adj[u] and color[v] = WHITE
14 then color[v] ←GRAY
15 [v] ←u
16 d[v] ← time← time +1
17 PUSH(S, v)
18 else color[u] ← BLACK
19 f [u] ← time ← time +1
20 POP(S)
21 return d, f, and 
第10页，共39页，编辑于2022年，星期五
DFS施于一个有向图的过程
第11页，共39页，编辑于2022年，星期五
3．算法的运行时间
DFS的运行时间如何？第1～2行的循环Θ(V)。内嵌于第14～20行操作对G的每条边执行一次，因此耗时
所以DFS的运行时间为Θ(V + E)。
第12页，共39页，编辑于2022年，星期五
有向无圈图的拓扑排序
DFS算法可以修改成能对各条边在遇到它们时进行分类。关键的思想是，每一条边(u, v)在首次被探索时可以根据顶点v的颜色来分类（但是进边和跨边不能区分）：
白色（WHITE）意味着一条树枝边；
灰色（GRAY）意味着一条回边；
黑色（BLACK）意味着一条进边或跨边。
图G是无圈的充分必要条件是G的一次深度优先搜索不产生回边。
第13页，共39页，编辑于2022年，星期五
问题的理解与描述
一个有向无圈图G = <V, E>（DAG）的拓扑排序是其所有顶点的一个线性排列，使得若边(u, v)包含在G中，则u在排列中必出现在v前（若图不是无圈的，则不可能有此线性排列）。一个图的拓扑排序可被视为将图的所有顶点水平排列时，所有的有向边从左指向右。
输入：有向图G。
输出：若G是DAG，输出G的各顶点的一个拓扑排序，否则输出出错信息。
第14页，共39页，编辑于2022年，星期五
算法的伪代码描述
TOPLOGICAL-SORT(G)
1 for each vertex uV[G]
2 do color[u]←WHITE
3 acyclicity←true
4 top-logic←S←
5 for each vertex s V[G]
6 do if color[s] = WHITE
7 then color[s] ← GRAY
8 PUSH(S, s)
9 while S≠
10 do u←TOP(S)
11 if v Adj[u] and color[v] = GRAY
12 then acyclicity←false
13 if v Adj[u] and color[v] = WHITE
14 then color[v] ←GRAY
15 PUSH(S, v)
16 else color[u] ← BLACK
17 PUSH(top-logic, u)
18 POP(S)
19 if acyclicity=true
20 then return top-logic
21 else print "G is not a DAG!“
由于TOPLOGICAL-SORT的运行时间与DFS的运行时间一致，所以，可以在时间Θ(V + E)内计算有向无圈图G=<V, E>的拓扑排序。
第15页，共39页，编辑于202