TopologicalSorting.java

packageGraph;

importjava.util.ArrayList;
importjava.util.LinkedList;

publicclassTopologicalSorting {

publicstaticvoidmain(String[] args) {

inttotalVertices = 6; // test graph 1
// int totalVertices = 3; // test graph 2
ArrayList<ArrayList<Integer>> adjList = newArrayList<ArrayList<Integer>>(totalVertices);
for (inti = 0; i < totalVertices; i++) {
adjList.add(newArrayList<Integer>(i));
 }
// test graph 1, output: 0 2 1 3 5 4
addEdge(adjList, 0, 1);
addEdge(adjList, 0, 2);
addEdge(adjList, 1, 3);
addEdge(adjList, 2, 3);
addEdge(adjList, 3, 4);
addEdge(adjList, 3, 5);

// test graph 2, output: 0 2 1
// addEdge(adjList, 0, 1);
// addEdge(adjList, 0, 2);

display(adjList);

System.out.println("\ntopological sorting...");
topologicalSort(adjList);
 }

privatestaticvoidaddEdge(ArrayList<ArrayList<Integer>> adjList, intu, intv) {
adjList.get(u).add(v); // directed graph Edge
 }

privatestaticvoiddisplay(ArrayList<ArrayList<Integer>> adjList) {
for (inti = 0; i < adjList.size(); i++) {
System.out.println(i + ": " + adjList.get(i));
 }
 }

// O(V+E) Time, DFS based approach
publicstaticvoidtopologicalSort(ArrayList<ArrayList<Integer>> adjList) {
// use addFirst() and removeFirst() method of LinkedList for O(1) Time
LinkedList<Integer> stack = newLinkedList<>();

boolean[] visited = newboolean[adjList.size()];

for (intvtx = 0; vtx < adjList.size(); vtx++) {
if (visited[vtx] == false) {
dfsTraverse(adjList, vtx, stack, visited);
 }
 }

while (!stack.isEmpty()) {
System.out.print(stack.removeFirst() + " "); // pop
 }
 }

privatestaticvoiddfsTraverse(ArrayList<ArrayList<Integer>> adjList, intvertex, LinkedList<Integer> stack,
boolean[] visited) {

visited[vertex] = true;

for (Integerneighbor : adjList.get(vertex)) {
if (visited[neighbor] == false) {
dfsTraverse(adjList, neighbor, stack, visited);
 }
 }
stack.addFirst(vertex); // push
 }
}