Topological Sorting

A topological sorting of a directed graph G is a linear ordering of its vertices such that for every directed edge u->v, u comes before v in the ordering. A topological sorting is possible if and only if the graph has no directed cycles i.e., it is a Directed Acyclic Graph (DAG). It is always possible to find a topological order for a DAG and this can be done in linear time.

Topological sorting of a DAG can be found with DFS. During the depth-first traversal of the graph, just when a vertex finishes expanding (i.e., all its outlinks have been visited), add it to a stack. The order of vertices in the stack represents the topological order of the DAG.

Pseudocode for topological sorting :

	Let L be an empty list
	Let all vertices be initially unmarked
	while there are unmarked vertices:
	select an unmarked vertex u
	dfs(u)
	def dfs(vertex u):
	mark u
	foreach edge u -> v
	if v is unmarked:
	dfs(v)
	add u to head of L
	L represents the topological order of the DAG

view raw Topological Sorting.py hosted with ❤ by GitHub

Thus, the time complexity of finding topological sorting is same as that of DFS i.e., O(V + E).

Take a look at C++ implementation.

Try your hand at problems TOPOSORT and RPLA, which use this idea.

Reference: Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne