Given a directed acyclic graph (DAG), print it in Topological order. If the DAG has more than one topological ordering, print 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, **

The graph shown above 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.

**Related Posts** –

Types of edges involved in DFS and relation between them

Arrival and Departure Time of Vertices in DFS

We can use DFS to solve this problem. **The idea is to order the vertices in order of their decreasing departure time 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] > 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**).

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 8 // data structure to store graph edges struct Edge { int src, dest; }; // class to represent a graph object class Graph { public: // A array of vectors to represent adjacency list vector<int> adjList[N]; // Constructor Graph(vector<Edge> edges) { // add edges to the Directed graph for (unsigned i = 0; i < edges.size(); i++) { int src = edges[i].src; int dest = edges[i].dest; adjList[src].push_back(dest); } } }; // Perform DFS on graph and set departure time of all // vertices of the graph int DFS(Graph const &graph, int v, vector<bool> &discovered, vector<int> &departure, int& time) { // mark current node as discovered discovered[v] = true; // set arrival time time++; // do for every edge (v -> u) for (int u : graph.adjList[v]) { // u is not discovered if (!discovered[u]) DFS(graph, u, discovered, departure, time); } // ready to backtrack // set departure time of vertex v departure[time] = v; time++; } // performs Topological Sort on a given DAG void doTopologicalSort(Graph const& graph) { // departure[] stores vertex number having its depature // time equal to the index of it vector<int> departure(2*N, -1); // Note if we had done the other way around i.e. fill // array with depature time by using vertex number // as index, we would need to sort the array later // stores vertex is discovered or not vector<bool> discovered(N); int time = 0; // perform DFS on all undiscovered vertices for (int i = 0; i < N; i++) if (!discovered[i]) DFS(graph, i, discovered, departure, time); // Print the vertices in order of their decreasing // departure time in DFS i.e. in topological order for (int i = 2*N - 1; i >= 0; i--) if (departure[i] != -1) cout << departure[i] << " "; } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 6}, {1, 2}, {1, 4}, {1, 6}, {3, 0}, {3, 4}, {5, 1}, {7, 0}, {7, 1} }; // create a graph from edges Graph graph(edges); // perform Topological Sort doTopologicalSort(graph); return 0; } |

**Output: **

7 5 3 1 4 2 0 6

**Time complexity** of above solutions is O(n + m) where n is number of vertices and e is number of edges in the graph.

**References:**

https://en.wikipedia.org/wiki/Topological_sorting

Dr. Naveen garg, IIT-D (Lecture – 29 DFS in Directed Graphs)

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂