How do I check if a directed graph is acyclic?

Question

How do I check if a directed graph is acyclic? And how is the algorithm called? I would appreciate a reference. Niko

Answer 1

The solution given by ShuggyCoUk is incomplete because it might not check all nodes.

def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

This has timecomplexity O(n+m) or O(n^2)

Answer 2

Doing a simple depth-first-search is not good enough to find a cycle. It is possible to visit a node multiple times in a DFS without a cycle existing. Depending on where you start, you also might not visit the entire graph.

You can check for cycles in a connected component of a graph as follows. Find a node which has only outgoing edges. If there is no such node, then there is a cycle. Start a DFS at that node. When traversing each edge, check whether the edge points back to a node already on your stack. This indicates the existence of a cycle. If you find no such edge, there are no cycles in that connected component.

As Rutger Prins points out, if your graph is not connected, you need to repeat the search on each connected component.

As a reference, Tarjan's strongly connected component algorithm is closely related. It will also help you find the cycles, not just report whether they exist.

Answer 3

I would try to sort the graph topologically, and if you can't, then it has cycles.

Answer 4

Lemma 22.11 on the Book Introduction to Algorithms (Second Edition) states that:

"A directed graph G is acyclic if and only if a depth-first search of G yields no back edges"