A  topological sort of a directed acylic graph (DAG)  G is an ordering of the vertices of  G such that for every edge (e_i, e_j) of  G  we have i < j. That is, a topological sort is a linear ordering of all its vertices such that if DAG  G  contains an edge (e_i, e_j), then e_i appears before e_j in the ordering. DAG is cyclic then no linear ordering is possible.

In simple words, a topological ordering is an ordering such that any directed path in DAG  G  traverses vertices in increasing order.

It is important to note that if the graph is not acyclic, then no linear ordering is possible. That is, we must not have circularities in the directed graph. For example, in order to get a job you need to have work experience, but in order to get work experience you need to have a job (sounds familiar?).

Theorem    A directed graph has a topological ordering if and only if it is acyclic.

Proof:

Part 1.  G has a topological ordering if is G acyclic.

Let  G is topological order.
Let  G has a cycle (Contradiction).
Because we have topological ordering. We must have  i₀, < i, < . . . < i_k-1 < i₀, which is clearly impossible.
Therefore,  G must be acyclic.

Part 2.  G is acyclic if has a topological ordering.

Let is  G acyclic.
Since  is  G acyclic, must have a vertex with no incoming edges. Let v₁ be such a vertex. If we remove v₁ from graph, together with its outgoing edges, the resulting digraph is still acyclic. Hence resulting digraph also has a vertex *

Algorithm Topological Sort

TOPOLOGICAL_SORT(G)

1. For each vertex find the finish time by calling DFS(G).
2. Insert each finished vertex into the front of a linked list.
3. Return the linked list.

Example

Given graph G; start node u

Diagram

with no incoming edges, and we let v₂ be such a vertex. By repeating this process until digraph G becomes empty, we obtain an ordering v₁ < v₂ < , . . . , v_n of vertices of digraph G. Because of the construction, if (v_i, v_j) is an edge of digraph G, then vi must be detected before v_j can be deleted, and thus i < j. Thus, v₁, . . . , v_n is a topological sorting.

Total running time of topological sort is (V + E) . Since DFS(G) search takes (V + E) time and it takes O(1) time to insert each of the |V| vertices onto the front of the linked list.