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.

Answer 1

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);
}

Answer 2

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

Answer 3

You can use inversion of finding cycle from my answer here https://stackoverflow.com/a/60196714/1763149

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

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

Answer 5

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 .

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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;
  }
  

Answer 10

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

Answer 11

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 12

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)