# What is topological sorting in a graph?

Topological sorting is a linear ordering of vertices such that for every directed edge ij, vertex i comes before j in the ordering.
Topological sorting is only possible for Directed Acyclic Graph (DAG).
Applications:
jobs scheduling from the given dependencies among jobs.
ordering of formula cell evaluation in spreadsheets
ordering of compilation tasks to be performed in make files,
data serialization
Topological Sort Code in Java:

`````` // V - total vertices
// visited - boolean array to keep track of visited nodes
// Main Topological Sort Function.
void topologicalSort()
{
Stack<Integer> stack = new Stack<Integer>();

// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
for (int j = 0; j < V; j++){
visited[j] = false;
}
// Call the util function starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);

// Print contents of stack -> result of topological sort
while (stack.empty() == false)
System.out.print(stack.pop() + " ");
}

// A helper function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
Stack<Integer> stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;

// Recur for all the vertices adjacent to the current vertex
Iterator<Integer> it = graph.get(v).iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack that saves result
stack.push(new Integer(v));
}``````

Topological sorting is sorting a set of n vertices such that every directed edge (u,v) to the vertex v comes from u ∈E(G) where u comes before v in the ordering.

A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Every DAG has at-least one topological ordering. There are algorithms to find topological ordering in O(m+n) time. One simple algorithm would be to do a DFS on a DAG. A possible topological order is obtained by ordering the vertices from higher to lower finish times of vertices in a DFS traversal