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

The following graph contains a cycle `0—1—3—0`, so it’s not DAG. If we remove edge `3–0` from it, it will become a DAG.

We can use Depth–first search (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 a directed graph, an edge is a back edge if `departure[u] < departure[v]`.

Proof: We have already discussed the relationship between all four types of edges involved in the DFS in the previous post. Following are the relationships we have seen between the departure time for different types of edges involved in a DFS of a directed graph:

Back edge (u, v):

`departure[u] < departure[v]`

Forward edge (u, v): departure[u] > departure[v]

Cross edge (u, v): departure[u] > departure[v]

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

The algorithm can be implemented as follows in C++, Java, and Python:

## 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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 #include #include using namespace std; // Data structure to store a graph edge struct Edge { int src, dest; }; // A class to represent a graph object class Graph { public: // a vector of vectors to represent an adjacency list vector> adjList; // Graph Constructor Graph(vector const &edges, int n) { // resize the vector to hold `n` elements of type `vector` adjList.resize(n); // add edges to the directed graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); } } }; // Perform DFS on the graph and set the departure time of all vertices of the graph int DFS(Graph const &graph, int v, vector &discovered, vector &departure, int &time) { // mark the current node as discovered discovered[v] = true; // do for every edge (v, u) for (int u: graph.adjList[v]) { // if `u` is not yet 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, int n) { // keep track of whether a vertex is discovered or not vector discovered(n); // keep track of the departure time of a vertex in DFS vector departure(n); int time = 0; // Perform DFS traversal from all undiscovered vertices // to visit all connected components of a graph for (int i = 0; i < n; i++) { if (!discovered[i]) { DFS(graph, i, discovered, departure, time); } } // check if the 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 the departure time of vertex `v` is greater than equal // to the departure time of `u`, 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; } int main() { // vector of graph edges as per the above diagram vector edges = { {0, 1}, {0, 3}, {1, 2}, {1, 3}, {3, 2}, {3, 4}, {3, 0}, {5, 6}, {6, 3} }; // total number of nodes in the graph (labelled from 0 to 6) int n = 7; // build a graph from the given edges Graph graph(edges, n); // check if the given directed graph is DAG or not if (isDAG(graph, n)) { cout << “The graph is a DAG”; } else { cout << “The graph is not a DAG”; } return 0; }

Output:
The graph is not a DAG

## Java

Output:
The graph is not a DAG

## Python

 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 # A class to represent a graph object class Graph: # Constructor def __init__(self, edges, n): # A list of lists to represent an adjacency list self.adjList = [[] for _ in range(n)] # add edges to the directed graph for (src, dest) in edges: self.adjList[src].append(dest) # Perform DFS on the graph and set the departure time of all vertices of the graph def DFS(graph, v, discovered, departure, time): # mark the current node as discovered discovered[v] = True # do for every edge (v, u) for u in graph.adjList[v]: # if `u` is not yet discovered if not discovered[u]: time = DFS(graph, u, discovered, departure, time) # ready to backtrack # set departure time of vertex `v` departure[v] = time time = time + 1 return time # Returns true if the given directed graph is DAG def isDAG(graph, n): # keep track of whether a vertex is discovered or not discovered = [False] * n # keep track of the departure time of a vertex in DFS departure = [None] * n time = 0 # Perform DFS traversal from all undiscovered vertices # to visit all connected components of a graph for i in range(n): if not discovered[i]: time = DFS(graph, i, discovered, departure, time) # check if the given directed graph is DAG or not for u in range(n): # check if (u, v) forms a back-edge. for v in graph.adjList[u]: # If the departure time of vertex `v` is greater than equal # to the departure time of `u`, 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 if __name__ == ‘__main__’: # List of graph edges as per the above diagram edges = [(0, 1), (0, 3), (1, 2), (1, 3), (3, 2), (3, 4), (3, 0), (5, 6), (6, 3)] # total number of nodes in the graph (labelled from 0 to 6) n = 7 # build a graph from the given edges graph = Graph(edges, n) # check if the given directed graph is DAG or not if isDAG(graph, n): print(‘The graph is a DAG’) else: print(‘The graph is not a DAG’)

Output:
The graph is not a DAG

The time complexity of the above solutions is O(V + E), where `V` and `E` are the total number of vertices and edges in the graph, respectively.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?

You are watching: Check if a digraph is a DAG (Directed Acyclic Graph) or not. Info created by GBee English Center selection and synthesis along with other related topics.