# Topological Sort Algorithm for DAG using DFS

Given a Directed Acyclic Graph (DAG), print it in topological order using Topological Sort Algorithm. If the DAG has more than one topological ordering, output any of them.

A Topological Sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, i.e. if the graph is DAG.

For example, consider below graph The graph has many valid topological ordering of vertices like,

5, 7, 3, 1, 0, 2, 6, 4
3, 5, 7, 0, 1, 2, 6, 4
5, 7, 3, 0, 1, 4, 6, 2
7, 5, 1, 3, 4, 0, 6, 2
5, 7, 1, 2, 3, 0, 6, 4
3, 7, 0, 5, 1, 4, 2, 6
etc.

Note that for every directed edge u -> v, u comes before v in the ordering. We can use Depth First Search (DFS) to implement Topological Sort Algorithm. The idea is to order the vertices in order of their decreasing Departure Time of Vertices in DFS and we will get our desired topological sort.

How does this work?

We have already discussed about the relationship between all four types of edges involved in the DFS in the previous post. Below are the relation we have seen between the departure time for different types of edges involved in a DFS of directed graph –

Tree edge (u, v): departure[u] > departure[v]
Back edge (u, v): departure[u] < departure[v]
Forward edge (u, v): departure[u] > departure[v]
Cross edge (u, v): departure[u] > departure[v]

As we can see that for a tree edge, forward edge or cross edge (u, v), departure[u] is more than departure[v]. But only for back edge the relationship departure[u] < departure[v] is true. So it is guaranteed that if an edge (u, v) has departure[u] > departure[v], it is not a back-edge.

We know that in DAG no back-edge is present. So if we order the vertices in order of their decreasing departure time, we will get topological order of graph (every edge going from left to right). Below is C++/Java implementation of Topological Sort Algorithm:

## Java

Output:

7 5 3 1 4 2 0 6

The time complexity of above implementation is O(n + m) where n is number of vertices and m is number of edges in the graph.

Also See: Kahn’s Topological Sort Algorithm

References:     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Smith Jones

DId you mean to say `departure[v] = time` instead of `departure[time] = v` in line 49? Guest

sorry, still not figure out how to paste code.