# 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.

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.,

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.