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.

Selah

Another case in favor of some way to "fix" wrong answers on SO. – Bresee

So, umm, I am mostly interested in the time needed to find it. So, I just need the abstract algorithm. – Selah

you must traverse all edges and check all vertices so lower bound is O(|V| + |E|). DFS and BFS are both the same complexity but DFS is easier to code if you have recursion as that manages the stack for you... – Macule

DFS is not the same complexity. Consider the graph with nodes { 1 .. N }, and edges in the form { (a, b) | a < b }. That graph is acyclic, and yet DFS would be O(n!) – Pythagorean

DFS is never O(n!). It visits each node once and each edge at most twice. So O(|V|+|E|) or O(n). – Fellows

I suppose we are talking about two separate implementations of DFS. Given nodes A,B,C,D and the encoding two comments above, what would the algorithm that generates the following be? A, AB, ABC, ABCD, ABD, ACD, AD. It advances depth first, and backtracks. Otherwise, you can't detect cycles. – Pythagorean

My DFS comment was me stupidly thinking in terms od Undirected graphs – Macule

Answer 1

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

Pythagorean

How did this have no votes?? It's linear on nodes + edges, far superior to the O(n^2) solutions! – Chastitychasuble

In many cases, a DFS (see J.Conrod's answer) may be easier, especially if a DFS needs to be performed anyway. But of course this depends on the context. – Editor

The topological ordering will be in an infinite loop but it would not say us where the cycle occurs... – Nine

Maybe its pretty old right now, but the way you mark the vertex visited during a DFS can tell you if the graph contains a cycle or not. If the vertex is visited during top down, mark visited as open, and mark it closed while going bottom up. If you visit an open vertex, it means the graph contains a cycle, otherwise not. – Tricolor

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.

Fellows

BTW: An edge that "points back to a node already on your stack" is often called a "back edge" in the literature, for obvious reasons. And yes, this may be simpler than sorting the graph topologically, especially if you need to do a DFS anyway. – Editor

For the graph to be acyclic, you say that each connected component must contain a node with only outgoing edges. Can you recommend an algorithm to find the connected components (as opposed to "strongly" connected components) of a directed graph, for use by your main algorithm? – Omophagia

@kostmo, if the graph has more than one connected component, then you will not visit all the nodes in your first DFS. Keep track of the nodes you've visited, and repeat the algorithm with unvisited nodes until you reach them all. This is basically how a connected components algorithm works anyway. – Fellows

While the intent of this answer is correct, the answer is confusing if using a stack-based implementation of DFS: the stack used to implement DFS will not contain the correct elements to test against. It's necessary to add an additional stack to the algorithm used to keep track of the set of ancestor nodes. – Micro

I have multiple questions about your answer. I posted them here: #37583099 – Lection

Answer 3

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

Starryeyed

This is basically just an abbreviated version of Jay Conrod's answer :-). – Editor

One of the problems from the same book seems to suggest there is a |V| time algorithm. It is answered here: #526831 – Premeditation

Answer 4

Solution1： Kahn algorithm to check cycle. Main idea: Maintain a queue where node with zero in-degree will be added into queue. Then peel off node one by one until queue is empty. Check if any node's in-edges are existed.

Solution2: Tarjan algorithm to check Strong connected component.

Solution3: DFS. Use integer array to tag current status of node: i.e. 0 --means this node hasn't been visited before. -1 -- means this node has been visited, and its children nodes are being visited. 1 -- means this node has been visited, and it's done. So if a node's status is -1 while doing DFS, it means there must be a cycle existed.

Fluidize

Answer 5

Just had this question in a Google interview.

Topological Sort

You can try to sort topologically, which is O(V + E) where V is the number of vertices, and E is the number of edges. A directed graph is acyclic if and only if this can be done.

Recursive Leaf Removal

The recursively remove leaf nodes until there are none left, and if there's more than a single node left you've got a cycle. Unless I'm mistaken, this is O(V^2 + VE).

DFS-style ~ O(n + m)

However, an efficient DFS-esque algorithm, worst case O(V + E), is:

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(child) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}

Tussis

Answer 6

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)

Umbrageous

mine is indeed incorrect - I deleted it though so your's now seems a little out of context – Macule

O(n+m) <= O(n+n) = O(2n), O(2n) != O(n^2) – Milson

@Artru O(n^2) when using adjacency matrix, O(n + m) when using adjacency list for representing the graph. – Horsecar

Um... m = O(n^2) since the complete graph has exactly m=n^2 edges. So that's O(n+m) = O(n + n^2) = O(n^2). – Schorl

Answer 7

I know this is an old topic but for future searchers here is a C# implementation I created (no claim that it's most efficient!). This is designed to use a simple integer to identify each node. You can decorate that however you like provided your node object hashes and equals properly.

For Very deep graphs this may have high overhead, as it creates a hashset at each node in depth (they are destroyed over breadth).

You input the node from which you want to search and the path take to that node.

• For a graph with a single root node you send that node and an empty hashset
• For a graph having multiple root nodes you wrap this in a foreach over those nodes and pass a new empty hashset for each iteration

• When checking for cycles below any given node, just pass that node along with an empty hashset

  private bool FindCycle(int node, HashSet<int> path)
  {
  
      if (path.Contains(node))
          return true;
  
      var extendedPath = new HashSet<int>(path) {node};
  
      foreach (var child in GetChildren(node))
      {
          if (FindCycle(child, extendedPath))
              return true;
      }
  
      return false;
  }
  

Hemimorphic

Answer 8

There should not be any back edge while doing DFS.Keep track of already visited nodes while doing DFS,if you encounter a edge between current node and existing node,then graph has cycle.

Protectorate

Answer 9

here is a swift code to find if a graph has cycles :

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

The idea is like this : a normal dfs algorithm with an array to keep track of visited nodes , and an additional array which serves as a marker for the nodes that led to the current node,so that when ever we execute a dfs for a node we set its corresponding item in the marker array as true ,so that when ever an already visited node encountered we check if its corresponding item in the marker array is true , if its true then its one of the nodes that let to itself (hence a cycle) , and the trick is whenever a dfs of a node returns we set its corresponding marker back to false , so that if we visited it again from another route we don't get fooled .

Synodic

Answer 10

Here is my ruby implementation of the peel off leaf node algorithm.

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

Payday

Answer 11

Here my implementation in pseudocode:

bool Acyclacity_Test
   InitColor() //Sets to WHITE every vertex
   while there is a node v in V:
      if (v.color == WHITE) then
         tmp = Aux_Acy(v);
         if ( not tmp ) return false
   return true
END

bool Aux_Acy(u)
   u.color = GREY
   for each node v in Adj(u)
       if(v.color == GREY) return false
       else if(v.color == WHITE) tmp = Aux_Acy(v)
       if(!tmp) return false;
   u.color = BLACK
   return true
END

Featherweight

Answer 12

You can use inversion of finding cycle from my answer here https://mcmap.net/q/36633/-how-to-detect-a-cycle-in-a-directed-graph-with-python

def is_acyclic(graph):
    return not has_cycle(graph)

Dorie