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:
C++
|
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 |
#include <iostream> #include <vector> using namespace std; // Data structure to store graph edges struct Edge { int src, dest; }; // Class to represent a graph object class Graph { public: // construct a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int N) { // resize the vector to N elements of type vector<int> adjList.resize(N); // add edges to the Directed graph for (auto &edge: edges) adjList[edge.src].push_back(edge.dest); }}; // Perform DFS on graph and set departure time of all // vertices of the graph void 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, int N) { // departure[] stores the vertex number using departure time as index vector<int> departure(2*N, -1); // Note if we had done the other way around i.e. fill the // array with departure 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] << " "; } // Topological Sort Algorithm for a DAG using DFS 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} }; // Number of nodes in the graph int N = 8; // create a graph from edges Graph graph(edges, N); // perform Topological Sort doTopologicalSort(graph, N); return 0; } |
Java
|
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
import java.util.*; // Data structure to store graph edges class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } }; // Class to represent a graph object class Graph { // An array of Lists to represent adjacency list List<List<Integer>> adjList = null; // Constructor Graph(List<Edge> edges, int N) { // allocate memory adjList = new ArrayList<>(N); for (int i = 0; i < N; i++) { adjList.add(i, new ArrayList<>()); } // add edges to the undirected graph for (int i = 0; i < edges.size(); i++) { int src = edges.get(i).source; int dest = edges.get(i).dest; // add an edge from source to destination adjList.get(src).add(dest); } } } class TopologicalSort { // Perform DFS on graph and set departure time of all // vertices of the graph static int DFS(Graph graph, int v, boolean[] discovered, 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.get(v)) { // u is not discovered if (!discovered[u]) { time = DFS(graph, u, discovered, departure, time); } } // ready to backtrack // set departure time of vertex v departure[time] = v; time++; return time; } // performs Topological Sort on a given DAG public static void doTopologicalSort(Graph graph, int N) { // departure[] stores the vertex number using departure time as index int[] departure = new int[2*N]; Arrays.fill(departure, -1); // Note if we had done the other way around i.e. fill the // array with departure time by using vertex number // as index, we would need to sort the array later // stores vertex is discovered or not boolean[] discovered = new boolean[N]; int time = 0; // perform DFS on all undiscovered vertices for (int i = 0; i < N; i++) { if (!discovered[i]) { time = 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) { System.out.print(departure[i] + " "); } } } // Topological Sort Algorithm for a DAG using DFS public static void main(String[] args) { // vector of graph edges as per above diagram List<Edge> edges = Arrays.asList( new Edge(0, 6), new Edge(1, 2), new Edge(1, 4), new Edge(1, 6), new Edge(3, 0), new Edge(3, 4), new Edge(5, 1), new Edge(7, 0), new Edge(7, 1) ); // Set number of vertices in the graph final int N = 8; // create a graph from edges Graph graph = new Graph(edges, N); // perform Topological Sort doTopologicalSort(graph, N); } } |
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. Topological Sorting – Wikipedia
2. Dr. Naveen garg, IIT-D (Lecture – 29 DFS in Directed Graphs)
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
DId you mean to say
departure[v] = timeinstead ofdeparture[time] = vin line 49?Thanks for sharing your concerns. The code is correct. departure[] stores the vertex number using departure time as index. If we had done the other way around i.e. fill the array with departure time by using vertex number as index, we would need to sort the array later. This is already mentioned in the comments.
sorry, still not figure out how to paste code.
Kindly enclose your code within <pre></pre> tags or run your code on an online compiler and share the link here.