#2. Topological Sort

Topological sort的概念只针对DAG! 有环的有向图也不行!

#2.1 DFS Topological Sort

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
public static List<Integer> topologicalSortDFS(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final List<Integer> res = new LinkedList<>();
final Map<Integer, Integer> visited = new HashMap<>();
for (final int v : graph.keySet()) {
if (!visited.contains(v)) {
dfs(v, graph, visited, res);
}
}
return res;
}
private static void dfs(final int v, final Map<Integer, Set<Integer>> graph, final Map<Integer, Integer> visited, final List<Integer> res) {
visited.putIfAbsent(v, 0);
final int status = visited.get(v);
if (status == 1) return;
if (status == -1) throw IllegalArgumentException("The given graph is not a DAG");
visited.put(v, -1);
for (final int adj : graph.get(v)) {
dfs(adj, graph, visited, res);
}
visited.put(v, 1);
res.add(0, v);
}

Python

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
import collections
# Topological sort is only for DAG!
# DFS topological sort
def topo_sort_dfs(graph):
"""
:graph Dict:
:rtype: List
"""
res = []
if not graph:
return res
visited = collections.defaultdict(int)
for v in graph:
if visited[v] == 0:
dfs(graph, v, visited, res)
return res[::-1]
def dfs(graph, v, visited, res):
"""
:graph Dict:
:v int:
:visited set:
:res List:
"""
if v not in graph:
raise Exception("invalid vertex")
elif visited[v] == 1:
return
elif visited[v] == -1:
raise Exception("the graph has cycle")
visited[v] = -1
for adj in graph[v]:
if visited[adj] == 0:
dfs(graph, adj, visited, res)
visited[v] = 1
res.append(v)

#2.2 BFS Topological Sort

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
public static List<Integer> topologicalSortBFS(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final Map<Integer, Integer> indegrees = new HashMap<>();
for (final int v : graph.keySet()) {
indegrees.putIfAbsent(v, 0);
for (final int adj : graph.get(v)) {
indegrees.putIfAbsent(adj, 0);
indegrees.put(adj, indegrees.get(adj) + 1);
}
}
final Queue<Integer> queue = new LinkedList<>();
for (final int v : graph.keySet()) {
if (indegrees.get(v) == 0) {
queue.offer(v);
}
}
while (!queue.isEmpty()) {
final int front = queue.poll();
res.add(front);
for (final int adj : graph.keySet()) {
indegrees.put(adj, indegreees.get(adj) - 1);
if (indegrees.get(adj) == 0) {
queue.offer(adj);
}
}
}
return res;
}

Python

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
import collections
# Topological sort is only for DAG!
def topo_sort_bfs(graph):
"""
:graph Dict:
:rtype: List
"""
res = []
if not graph:
return res
indegree = collections.defaultdict(int)
for v in graph:
for adj in graph[v]:
indegree[adj] += 1
visited = set()
q = collections.deque()
for v in graph:
if indegree[v] == 0:
visited.add(v)
q.append(v)
while q:
size = len(q)
for _ in range(size):
v = q.popleft()
res.append(v)
for adj in graph[v]:
indegree[adj] -= 1
if indegree[adj] == 0 and adj not in visited:
visited.add(adj)
q.append(adj)
for v in indegree:
if indegree[v] != 0:
raise Exception("the graph has cycle")
return res[::-1]

Comments

01/03/2020