Topological Sort

Topological sort is applicable on directed acyclic graphs only. So let us first understand what we mean by the directed acyclic graph.

Directed Acyclic Graph

A graph is called a Directed Acyclic Graph (DAG) if the graph is a directed graph and it has no directed cycles. DAG is used to find common subexpressions in optimizing compilers. The graph shown below is an example of a directed acyclic graph.

Working Mechanism

• Topological sorting of directed graph is linear ordering of its vertices. In this sorting, for every directed edge from u to v, u comes before v in ordering. This is used to simulate tasks and their ordering. In graph, each node may represent one task and every edge may represent constraint that one task should be complete before another.
• Topological sorting is possible only if graph is DAG. Every DAG has at least one topological sorting sequence. If graph is not DAG, topological sorting is not possible.
• Topological sorting is different than DFS. In topological sorting, vertex is print before its adjacent vertices.
• In simplest way, to find topological ordering of graph, we should perform following steps :
  • Visit graph in DFS order and label the vertices with their discovery and finish time.
  • Linearly arrange vertices in decreasing order of their finish time from left to right
  • Join the vertices using forward arcs in linear ordering, corresponding to graph

• There may exist more than one DFS forest of graph, so multiple topological ordering for same graph is possible. Arc can only go in forward direction. For above graph, two different DFS traversal and their linear ordering is shown below :

Algorithm for Topological Sort

The algorithm for topological sorting is shown below:

Algorithm

TOPOLOGICAL_SORT
// Input to algorithm is graph G = <V, E>

Call DFS
Display vertices in decreasing order of their finish time

Complexity Analysis

This algorithm scans edges and nodes once to order them. So running time is linear in a number of edges and vertices, i.e. O(|V| + |E|).

Applications of Topological Sort

• Project management.
• Event management.
• Job scheduling.
• Instruction scheduling.
• Order of compilation tasks.
• Data serialization.
• Ordering of cell evaluation in formulas in spread sheet.

---

Additional Reading: [Wiki]