Check if given digraph is a DAG (Directed Acyclic Graph) or not

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

1. Types of edges involved in DFS and relation between them

2. 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].

  Types of edges involved in DFS and relation between them


Download   Run Code


Graph is not DAG


Download   Run Code


Graph is not DAG

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

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)


Thanks for reading.

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 :)

Leave a Reply

Notify of