**Topological Sort in Java**

Topological sortis mainly used in the linear ordering of vertices in a Directed Acyclic Graph (DAG). **Topological sort in Java** illustrates how to do the linear ordering of vertices in programming. Here linear ordering of vertices means for every two nodes of the directed acyclic graph, v and u, such that v -> u, node v should always come before u.

**Algorithm & Pseudo Code**

**Step I:** Create the graph by calling createEdge(‘x’,’y’).

**Step II:** Call the topologicalSorting( )

- Make a Boolean array (named as visit[ ]) and a stack ;
**b:**Populate the ‘false’ value to all the elements of the vist[] array. The ‘false’ value of an element means that the element is not visited.- Invoke the helping function topologicalSortUtility() recursively to keep track of the Topological Sort beginning from all the vertices one by one.

**Step III:** Define topologicalSortUtil(char node, bool visit[], stack<Character> &stk):

- Update the Boolean array visit by marking the current node as visited, i.e., ‘true’ value should be added corresponding to the current node.

1 2 3 |
visit[i] = true |

- Visit all the vertices adjacent to the current vertex by recursively calling the topologicalSortUtility() method. Ensure that recursion only happens when the adjacent vertex is not visited, i.e.,

1 2 3 4 5 6 |
if (visit[j] == false) { topologicalSortUtility(j, visit, stk); } |

- In order to store the result, add the current vertex to the stack.

**Step IV:** In the end, after returning from the helping function, display the contents of the stack.

**Java Program**The following code implements Topological sort using the algorithm defined above. The code does the implementation of the following direct acyclic graph.

**FileName**: TopologicalSortExample.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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// A Java program that implements Topological sorting on Directed Acyclic Graph import java.io.*; import java.util.*; // A Java program that implements Topological sorting on Directed Acyclic Graph import java.io.*; import java.util.*; // The following class implements a directed acyclic graph // represented by using an adjacency list class DirectedAcyclicGraph { // Total number of vertices present in the graph private int noOfVertices; // Adjacency List comprising of ArrayList of ArrayList's private ArrayList<ArrayList<Character> > adjList; // Paramterized Constructor DirectedAcyclicGraph(int noOfNodes) { noOfVertices = noOfNodes; // creating the the adjecency list adjList = new ArrayList<ArrayList<Character> >(noOfNodes); for (int i = 0; i < noOfNodes; ++i) { adjList.add(new ArrayList<Character>()); } } // Method to create an edge between two nodes of the Directed Acyclic Graph void createEdge(Character v, Character w) { adjList.get((int)(v - 65)).add(w); } // A method that visits the nodes that are adjacent to the current node using recursion void topologicalSortUtility(char node, boolean visited[], Stack<Character> stk) { // Marking the current node as visited by setting its value to false visited[(int)(node - 65)] = true; Character j; // An iterator for iterating through the adjacency list Iterator<Character> itr = adjList.get((int)(node - 65)).iterator(); while (itr.hasNext()) { // fetching the adjacent node j = itr.next(); // adjacent node must not be visited if (visited[(int)(j - 65)] == false) { // recursively traversing the adjecent nodes topologicalSortUtility(j, visited, stk); } } // Pushing current node to the stack // that fetches the result stk.push(new Character(node)); } // A method that does Topological Sorting. // It uses recursive method topologicalSortUtility() void topologicalSorting() { // creating a stack Stack<Character> stk = new Stack<Character>(); // creating a boolean array of size equal to number of vertices boolean visited[] = new boolean[noOfVertices]; // At First, marking all the nodes as not visited, by assigning false value for (int i = 0; i < noOfVertices; i++) { visited[i] = false; } // Call the utility method topologicalSortUtility() // on every node that is not visited for (int j = 0; j < noOfVertices; j++) { if (visited[j] == false) { topologicalSortUtility((char)(j + 65), visited, stk); } } // Displaying contents of the stack while (stk.empty() == false) { System.out.print(stk.pop() + " "); } } } public class TopologicalSortExample { // Main Method public static void main(String argvs[]) { // Creating an object of DirectedAcyclicGraph DirectedAcyclicGraph g = new DirectedAcyclicGraph(6); g.createEdge('F', 'C'); // F -> C g.createEdge('F', 'A'); // F -> A g.createEdge('E', 'A'); // E -> A g.createEdge('E', 'B'); // E -> B g.createEdge('C', 'D'); // C -> D g.createEdge('D', 'B'); // D -> B System.out.println("Topological sort of the nodes " + "present in the graph defined above is: " ); // Invoking the method topologicalSorting() g.topologicalSorting(); } } |

**Output**:

1 2 3 4 |
Topological sort of the nodes presents in the graph defined above is: F E C D B A |

**Explanation:** The parameterized constructor takes an argument that defines the number of nodes present in the graph. In the constructor, the adjacency list is also created. The createEdge() method updates the adjacency matrix whenever an edge is created between two nodes. The topologicalSortUtility() method uses this adjacency list to traverse through the elements that are adjacent to the current element.

Note that in the above code snippet, the number 65 is used frequently. The number 65 is the ASCII value of the letter ‘A’. Therefore, when (int)‘A’ – 65 is done, internally, ‘A’ gets converted to 65 and 65 – 65 = 0. Therefore, the letter ‘A’ points to the 0^{th} index of the Boolean array visited or 0^{th} row of the adjacency list. Similar logic for the other letters too. For converting numbers to the letter, 65 is added to the number then type casted into chars, i.e., (char)i + 65, where is also a number.

**Analysis of the Topological Sort**

Topological sort is opposite to the DFS (Depth First Search). In DFS, the farthermost adjacent is visited first, and then we move backward to visit the other nodes, whereas, in topological sort, the current node is visited before its adjacent nodes, which is achieved using a stack. Thus, the topological sort is DFS with the stack.

**Time Complexity**

Since the topological sort is DFS with stack, the time complexity of the topological sort is equal to the DFS, which is **O(V + E),** where V is the number of vertices, and E is total number of edges presented in the graph. Similar to DFS, topological sort also has the same best, worst as well as average time complexity, i.e., O(V + E).

**Space Complexity**

To store and print the nodes of the acyclic graph, a stack is used whose size can’t go beyond the total number of nodes present in the graph. Thus, space complexity is **O(n),** where n is the total number of elements present in the array. The O(n) space complexity is same for the best, worst as well as average cases.

**Conclusion**

Topological sort does the sorting on the basis of the ordering of the elements in the graph. For example, in the above graph, node F should always come before node A.

Thus, when there is a requirement that completion of work must be done before the other work, we need a topological sort to do the ordering.

For example, suppose there are two Java files *ABC.java*, which contains the class *ABC{}*, and *PQR.java*. Let’s assume that in the file *PQR.java*, one is creating an object of the class *ABC{}*. Therefore, the PQR.java file is dependent on the class *ABC{}*. Hence, the file ABC.java should be executed first, then the PQR.java.

In such kind of scenario, topological sorting is used. This type of sorting is mainly used in a compiler because a compiler has to decide which file to execute first and which one later.