-
Notifications
You must be signed in to change notification settings - Fork 2
/
StronglyConnectedComponentsKosarajuAlgorithm.java
73 lines (61 loc) · 1.82 KB
/
StronglyConnectedComponentsKosarajuAlgorithm.java
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package com.algorithm.playground.graph;
import java.util.*;
import java.util.Map.Entry;
import static com.algorithm.playground.utils.FunctionUtils.newArrayList;
import static java.util.Collections.emptyList;
/**
* An implementation for Kosaraju's Algorithm for finding strongly connected components
* based on an idea from this video:
* https://www.youtube.com/watch?v=RpgcYiky7uw&list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&index=9
*
* @param <V>
*/
public class StronglyConnectedComponentsKosarajuAlgorithm<V> {
public List<Set<V>> getComponents(Map<V, List<V>> graph) {
LinkedList<V> stack = new LinkedList<>();
Set<V> seen = new HashSet<>();
for (V curr : graph.keySet()) {
firstDFS(graph, seen, stack, curr);
}
Map<V, List<V>> reversed = reverse(graph);
List<Set<V>> components = new ArrayList<>();
LinkedList<V> dfs = new LinkedList<>();
seen.clear();
/** second dfs */
while (!stack.isEmpty()) {
V curr = stack.pop();
if (!seen.contains(curr)) {
dfs.push(curr);
Set<V> set = new HashSet<>();
while (!dfs.isEmpty()) {
V next = dfs.pop();
if (seen.add(next)) {
set.add(next);
for (V child : reversed.getOrDefault(next, emptyList())) {
dfs.push(child);
}
}
}
components.add(set);
}
}
return components;
}
private void firstDFS(Map<V, List<V>> graph, Set<V> seen, LinkedList<V> stack, V curr) {
if (seen.add(curr)) {
for (V next : graph.getOrDefault(curr, emptyList())) {
firstDFS(graph, seen, stack, next);
}
stack.push(curr);
}
}
private Map<V, List<V>> reverse(Map<V, List<V>> graph) {
Map<V, List<V>> reversed = new HashMap<>();
for (Entry<V, List<V>> entry : graph.entrySet()) {
for (V child : entry.getValue()) {
reversed.computeIfAbsent(child, newArrayList()).add(entry.getKey());
}
}
return reversed;
}
}