#3. Cycle Detection

#3.1 How to detect cycle?

  1. DFS
  2. BFS
  3. Topological Sort (Only for Directed Graph)

#3.1.1 DFS to Detect Cycle

利用递归. 不同于普通遍历, 判断是否有cycle的时候要利用一个HashMap来记录每个结点的状态.

1
2
3
0 - 未访问
1 - 访问结束
-1 - 访问过但还未结束

DFS Cycle Detection for Directed Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
Map<Integer, Integer> visited = new HashMap<>();
for (final int v : graph.keySet()) {
if (!visited.containsKey(v)) {
if (dfsHasCycle(v, graph, visited)) {
return true;
}
}
}
return false;
}
private static boolean dfsHasCycle(final int v, final Map<Integer, Set<Integer>> graph,
final Map<Integer, Integer> visited) {
final isVisited = visited.getOrDefault(v, 0);
if (isVisited == 1) return false;
if (isVisited == -1) return true;
visited.put(v, -1);
for (final int adj : graph.keySet()) {
if (dfsHasCycle(adj, graph, visited)) {
return true;
}
}
visited.put(v, 1);
return false;
}

DFS Cycle Detection for Undirected Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static void hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
Map<Integer, Integer> visited = new HashMap<>();
for (final int v : graph.keySet()) {
if (!visited.containsKey(v)) {
if (dfsHasCycle(v, graph, visited, v)) {
return true;
}
}
}
return false;
}
private static boolean dfsHasCycle(final int v, final Map<Integer, Set<Integer>> graph,
final Map<Integer, Integer> visited, final int parent) {
final isVisited = visited.getOrDefault(v, 0);
if (isVisited == 1) return false;
if (isVisited == -1) return true;
visited.put(v, -1);
for (final int adj : graph.keySet()) {
if (adj != parent) { // Only difference with Directed graph version.
if (dfsHasCycle(adj, graph, visited, v)) {
return true;
}
}
}
visited.put(v, 1);
return false;
}

#3.1.2 BFS to Detect Cycle

BFS Cycle Detection For Directed Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static boolean hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
// 不再像DFS那样需要-1, 0, 1三种状态. BFS只需要0和1两种,所以用一个HashSet就够了.
final Set<Integer> visited = new HashSet<>();
final Queue<Integer> queue = new LinkedList<>();
for (final int v : graph.keySet()) {
queue.offer(v);
while (!queue.isEmpty()) {
final int curr = queue.poll();
if (visited.contains(curr)) return true;
visited.add(curr);
for (final int adj : graph.get(curr)) {
if (visited.contains(curr)) return true;
queue.offer(adj);
}
}
}
return false;
}

BFS Cycle Detection For Undirected Graph

Solution: 记录访问情况

需要有个parent的HashMap来记录每个结点是经过谁过来的.

parent只需要是一个link, Map<Integer, Integer>即可, 不需要是一个Map<Integer, Set<Integer>>. 因为即使有多个结点v1, v2指向w, 因为是undirected graph的关系, 完全可以看做是v1指向w, w再指向v2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static boolean hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
// 不再像DFS那样需要-1, 0, 1三种状态. BFS只需要0和1两种,所以用一个HashSet就够了.
final Set<Integer> visited = new HashSet<>();
final Queue<Integer> queue = new LinkedList<>();
final Map<Integer, Integer> parent = new HashMap<>();
for (final int v : graph.keySet()) {
queue.offer(v);
while (!queue.isEmpty()) {
final int curr = queue.poll();
if (visited.contains(curr)) return true;
visited.add(curr);
for (final int adj : graph.get(curr)) {
if (parent.get(curr) == adj) continue;
if (visited.contains(curr)) return true;
// Update parent link
parent.put(adj, curr);
queue.offer(adj);
}
}
}
return false;
}

#3.1.3 Topological Sort to Detect Cycle

判断是否有cycle的思路是利用topological sort. 如果topological sort走完之后还有vertices的indegree大于0的话. 就说明是有环.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static boolean hasCycle(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
// Compute the indegree of all vertices
final Map<Integer, Integer> indgree = new HashMap<>();
for (final int v : graph.keySet()) {
indegree.putIfAbsent(v, 0);
for (final int adj : graph.get(v)) {
indegree.putIfAbsent(adj, 0);
indegree.put(adj, indegree.get(adj) + 1);
}
}
// Enqueue every vertex with 0 indegree
final Queue<Integer> queue = new LinkedList<>();
for (final int v : indegree) {
if (indegree.get(v) == 0) {
queue.offer(v);
}
}
// Topological sort
while (!queue.isEmpyt()) {
final int v = queue.poll();
for (final int adj : graph.get(v)) {
indegree.put(adj, indegree.get(adj) - 1);
if (indegree.get(adj) == 0) {
queue.offer(adj);
}
}
}
// Find out if any vertex still with non-zero indegree
for (final int v : indegree.keySet()) {
if (indegree.get(v) != 0) {
return true;
}
}
return false;
}

#3.2 How to detect negative cycle?

  1. Bellman-Ford
  2. Floyd-Warshall

See more details in Shortest Path Section

Comments

01/03/2020