Topological Sorting

Topological sorting is an ordering of the vertices of a directed graph such that if there is an edge a->b between vertices a and b, then a appears before b in the ordering. Consider the graph below:

One possible ordering is [4,1,5,2,3,6]

For a directed graph to have a topological ordering, it should not contain any cycle.

We can make use of DFS traversal to both check if the directed graph contains a cycle and, if doesn’t, to construct a topological sort.

Pseudo code for topological sort:

DFS(graph,u)
{
# state[u] = 1 => u has not been processed yet.
# state[u] = 2 => u is under processing.
# state[u] = 3 => u has been processed earlier.
	if(state[u]==3):
		return ;
	else if(state[u] = 2):
		cycle = 1;
		return ;
	else state[u] = 2;
	for every neighbour v of u:
		DFS(graph,v);
	
	state[u] = 3; # mark it processed.
	Stack.push(u);
}

topologicalSort(graph)
{
	ordering = []
	state[V] = {1};
	cycle = 0;
	stack Stack;
	for every node u in graph:
		DFS(graph,u);
		
	if cycle == 1:
		return ordering;
	
	while Stack is not Empty:
		ordering.add(Stack.top());
		Stack.pop();
	
	return ordering;
}

References: GeeksforGeeks