Skip to content

Commit 5fdd209

Browse files
giaunvgiaunv
committed
Topological Sort
1 parent a936850 commit 5fdd209

3 files changed

Lines changed: 205 additions & 0 deletions

File tree

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/TopologicalSortByDFSIterativeColor.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.hellokoding.datastructure.graph;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.ArrayList;
5+
import java.util.Deque;
6+
import java.util.List;
7+
8+
public class TopologicalSortByDFSIterativeColor {
9+
static final int WHITE = 0, GRAY = 1, BLACK = 2;
10+
11+
static List<Integer> topologicalSort(GraphDirectedByAdjacencyList g) {
12+
int[] color = new int[g.V];
13+
Deque<Integer> stack = new ArrayDeque<>(g.V);
14+
Deque<Integer> sorted = new ArrayDeque<>(g.V);
15+
16+
for (int i = 0; i < g.V; i++) {
17+
if (color[i] != WHITE) continue;
18+
stack.push(i);
19+
20+
while (!stack.isEmpty()) {
21+
int v = stack.peek();
22+
23+
if (color[v] == WHITE) {
24+
color[v] = GRAY;
25+
} else {
26+
color[v] = BLACK;
27+
sorted.push(stack.pop());
28+
}
29+
30+
for (int w : g.adjacencyList.get(v)) {
31+
if (color[w] == GRAY) {
32+
// Found a cycle
33+
return new ArrayList<>();
34+
} else if (color[w] == WHITE) {
35+
stack.push(w);
36+
}
37+
}
38+
}
39+
}
40+
41+
return new ArrayList<>(sorted);
42+
}
43+
44+
static void printResult(List<Integer> sorted) {
45+
if (sorted.isEmpty()) {
46+
System.out.println("There are no topological orderings as the input graph is cyclic");
47+
} else {
48+
sorted.forEach((x) -> System.out.printf("%d ", x));
49+
System.out.println();
50+
}
51+
}
52+
53+
public static void main(String[] args) {
54+
GraphDirectedByAdjacencyList g1 = new GraphDirectedByAdjacencyList(5);
55+
g1.addEdge(0, 1);
56+
g1.addEdge(1, 2);
57+
g1.addEdge(2, 0);
58+
g1.addEdge(1, 3);
59+
g1.addEdge(2, 4);
60+
printResult(topologicalSort(g1));
61+
62+
GraphDirectedByAdjacencyList g2 = new GraphDirectedByAdjacencyList(4);
63+
g2.addEdge(0, 1);
64+
g2.addEdge(2, 0);
65+
g2.addEdge(2, 1);
66+
g2.addEdge(3, 2);
67+
printResult(topologicalSort(g2));
68+
}
69+
}

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/TopologicalSortByDFSRecursiveColor.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package com.hellokoding.datastructure.graph;
2+
3+
import java.util.ArrayDeque;
4+
import java.util.ArrayList;
5+
import java.util.Deque;
6+
import java.util.List;
7+
8+
public class TopologicalSortByDFSRecursiveColor {
9+
static final int WHITE = 0, GRAY = 1, BLACK = 2;
10+
static boolean hasCycle = false;
11+
12+
static void topologicalSortByDFSRecursive(GraphDirectedByAdjacencyList g, int v, int[] color, Deque<Integer> stack) {
13+
if (hasCycle) {
14+
return;
15+
}
16+
17+
color[v] = GRAY;
18+
19+
for (Integer w : g.adjacencyList.get(v)) {
20+
if (color[w] == GRAY) {
21+
hasCycle = true;
22+
}
23+
24+
if (color[w] == WHITE) {
25+
topologicalSortByDFSRecursive(g, w, color, stack);
26+
}
27+
}
28+
29+
color[v] = BLACK;
30+
stack.push(v);
31+
}
32+
33+
static List<Integer> topologicalSort(GraphDirectedByAdjacencyList g) {
34+
int[] color = new int[g.V];
35+
Deque<Integer> stack = new ArrayDeque<>();
36+
hasCycle = false;
37+
38+
for (int i = 0; i < g.V; i++) {
39+
if (color[i] == WHITE) {
40+
topologicalSortByDFSRecursive(g, i, color, stack);
41+
}
42+
}
43+
44+
return hasCycle ? new ArrayList<>() : new ArrayList<>(stack);
45+
}
46+
47+
public static void printResult(List<Integer> sorted) {
48+
if (sorted.isEmpty()) {
49+
System.out.println("There are no topological orderings as the input graph is cyclic");
50+
} else {
51+
sorted.forEach((x) -> System.out.printf("%d ", x));
52+
System.out.println();
53+
}
54+
}
55+
56+
public static void main(String[] args) {
57+
GraphDirectedByAdjacencyList g1 = new GraphDirectedByAdjacencyList(5);
58+
g1.addEdge(0, 1);
59+
g1.addEdge(1, 2);
60+
g1.addEdge(2, 0);
61+
g1.addEdge(1, 3);
62+
g1.addEdge(2, 4);
63+
printResult(topologicalSort(g1));
64+
65+
GraphDirectedByAdjacencyList g2 = new GraphDirectedByAdjacencyList(4);
66+
g2.addEdge(0, 1);
67+
g2.addEdge(2, 0);
68+
g2.addEdge(2, 1);
69+
g2.addEdge(3, 2);
70+
printResult(topologicalSort(g2));
71+
}
72+
}

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/TopologicalSortByInDegree.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.hellokoding.datastructure.graph;
2+
3+
import java.util.*;
4+
5+
public class TopologicalSortByInDegree {
6+
static List<Integer> topologicalSortByInDegree(GraphDirectedByAdjacencyList g) {
7+
List<Integer> sorted = new ArrayList<>();
8+
int[] inDegree = new int[g.V];
9+
10+
for (int v = 0; v < g.V; v++) {
11+
for(int w : g.adjacencyList.get(v)) {
12+
inDegree[w] += 1;
13+
}
14+
}
15+
16+
Queue<Integer> queue = new ArrayDeque<>();
17+
for (int v = 0; v < g.V; v++) {
18+
if (inDegree[v] == 0) {
19+
queue.offer(v);
20+
}
21+
}
22+
23+
while (!queue.isEmpty()) {
24+
int v = queue.poll();
25+
sorted.add(v);
26+
27+
for (int w : g.adjacencyList.get(v)) {
28+
inDegree[w]--;
29+
30+
if (inDegree[w] == 0) {
31+
queue.offer(w);
32+
}
33+
}
34+
}
35+
36+
return sorted.size() == g.V ? sorted : new ArrayList<>();
37+
}
38+
39+
public static void printResult(List<Integer> sorted) {
40+
if (sorted.isEmpty()) {
41+
System.out.println("There are no topological orderings as the input graph is cyclic");
42+
} else {
43+
sorted.forEach((x) -> System.out.printf("%d ", x));
44+
System.out.println();
45+
}
46+
}
47+
48+
public static void main(String[] args) {
49+
GraphDirectedByAdjacencyList g1 = new GraphDirectedByAdjacencyList(5);
50+
g1.addEdge(0, 1);
51+
g1.addEdge(1, 2);
52+
g1.addEdge(2, 0);
53+
g1.addEdge(1, 3);
54+
g1.addEdge(2, 4);
55+
printResult(topologicalSortByInDegree(g1));
56+
57+
GraphDirectedByAdjacencyList g2 = new GraphDirectedByAdjacencyList(4);
58+
g2.addEdge(0, 1);
59+
g2.addEdge(2, 0);
60+
g2.addEdge(2, 1);
61+
g2.addEdge(3, 2);
62+
printResult(topologicalSortByInDegree(g2));
63+
}
64+
}

0 commit comments

Comments
 (0)