Given an directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.

Below graph contains a cycle A-B-D-A, so it is not DAG. If we remove edge 3-0 from it, it will become a DAG.

**Recommended Read** –

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 find if any back-edge is present in the graph or not.

**A digraph is a DAG if there is no back-edge present in the graph**. Recall that a back-edge is an edge from a vertex to one of its ancestors in the DFS tree.

**Fact**: For an edge u -> v in an directed graph, an edge is a back edge if departure[u] < departure[v].
**Proof:** We have already discussed about the relationship between all four types of edges involved in the DFS in 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]

If we note that for tree edge, forward edge and cross edge, departure[u] > departure[v]. But only for back edge the relationship departure[u] < departure[v] is true. So it is guaranteed that an edge (u, v) is a back-edge, not some other edge if departure[u] < departure[v].

**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 104 105 106 107 108 109 110 111 112 113 114 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 7 // 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; // 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[v] = time++; } // returns true if given directed graph is DAG bool isDAG(Graph const& graph) { // stores vertex is discovered or not vector<bool> discovered(N); // stores departure time of a vertex in DFS vector<int> departure(N); int time = 0; // Do DFS traversal from all undiscovered vertices // to visit all connected components of graph for (int i = 0; i < N; i++) if (discovered[i] == false) DFS(graph, i, discovered, departure, time); // check if given directed graph is DAG or not for (int u = 0; u < N; u++) { // check if (u, v) forms a back-edge. for (int v : graph.adjList[u]) { // If departure time of vertex v is greater // than equal to departure time of u, then // they form a back edge // Note that departure[u] will be equal to // departure[v] only if u = v i.e vertex // contain an edge to itself if (departure[u] <= departure[v]) return false; } } // no back edges return true; } // main function int main() { // vector of graph edges as per above diagram vector<Edge> edges = { {0, 1}, {0, 3}, {1, 2}, {1, 3}, {3, 2}, {3, 4}, {3, 0}, {5, 6}, {6, 3} }; // create a graph from edges Graph graph(edges); // check if given directed graph is DAG or not if (isDAG(graph)) cout << "Graph is DAG"; else cout << "Graph is not DAG"; return 0; } |

**Output: **

Graph is not DAG

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

**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 🙂