算法复习——图算法篇之图中环路的存在性判断_证明环中有后向边

算法复习——图算法篇之图中环路的存在性判断

以下内容主要参考中国大学MOOC《算法设计与分析》，墙裂推荐希望入门算法的童鞋学习！

1. 问题定义

有向图中环路的存在性判断

输入：

• 有向图$G=<V,E>$，$V$是顶点集合，$E$是边的集合

输出：

• 图$G$是否存在环

2. 猜想证明

​ 根据有向图中深度优先搜索边的性质，并研究实例，我们可以猜想有向图存在环路等价于搜索时出现后向边。

证明：

• 充分性：
  • 不妨设环路上被搜索的第一个点为$u$，$v$是在环路上指向$u$的点
  • $u$可达$v$，深度优先搜索可以搜索到$v$
  • 搜索$v$时，由于$v$指向$u$，必能再次发现顶点$u$
  • 从后代搜索祖先，出现后向边
• 必要性：
  • 深度优先树中祖先可达后代
  • 后向边从后代指向祖先
  • 后代和祖先之间存在环路

3. 伪代码

DFS-Judge-Cycle(G)

输入：图$G$

输出：是否存在环路

新建数组color[1..V],pred[1..V]
// 初始化
for v ∈ V do
	pred[v] ← NULL
	color[v] ← WHITE
end
for v ∈ V do
	if color[v] = WHITE then
		if DFS-Visit-Judge-Cycle(G, v) = TRUE then
			return TRUE
		end
	end
end
1
2
3
4
5
6
7
8
9
10
11
12
13

DFS-Visit-Judge-Cycle(G, v)

输入：图$G$，顶点$v$

输出：顶点$v$是否在某环路中

color[v] ← GRAY
for w ∈ G.Adj[v] do
	if color[w] = GRAY then
		return TRUE
	end
	if color[w] = WHITE then
		pred[w] ← v
		if DFS-Visit-Judge-Cycle(G, w) = TRUE then
			return TRUE
		end
	end
end
color[v] ← BLACK
return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14

​ 该算法的时间复杂度和深度优先搜索的时间复杂度一致，是$O(|V|+|E|)$。