How to detect if a directed graph is cyclic?

Question

How can we detect if a directed graph is cyclic? I thought using breadth first search, but I'm not sure. Any ideas?

Syst

possible duplicate of How do I check if a directed graph is acyclic? – Noun

I just posted an generic FP solution for Scala on a related StackOverflow thread: https://mcmap.net/q/534894/-scala-graph-cycle-detection-algo-39-return-39-needed – Commandeer

See my answer here: https://mcmap.net/q/36633/-how-to-detect-a-cycle-in-a-directed-graph-with-python – Conterminous

Answer 1

Usually depth-first search is used instead. I don't know if BFS is applicable easily.

In DFS, a spanning tree is built in order of visiting. If a the ancestor of a node in the tree is visited (i.e. a back-edge is created), then we detect a cycle.

See http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf for a more detailed explanation.

Functionalism

BFS or DFS have the same complexity (runtime) and applicability (same result) on this problem. The only difference is in the visiting order of the nodes. – Gammer

The last statement on the page indicated in the link is a topological statement based on the number of edges and vertices: "The maximum number of possible edges in the graph G if it does not have cycle is |V| - 1." This is true for undirected graphs, but not for directed graphs, as indicated in the original question. For directed graphs, the "diamond inheritance" diagram provides a counterexample (4 nodes and 4 edges make a "loop", but not a "cycle" that can be traversed by following the arrows). – Anglocatholic

In case the last comment wasn't clear - I'm saying that the accepted answer is sufficient for undirected graphs, but wrong for directed graphs (as specified in the question). – Anglocatholic

@Peter: The previous link maybe wrong, but the concept I've described is correct even for digraphs. I made the terminology clearer and provided a better source. – Functionalism

@darlinton: but it is an overkill to do BFS because the same thing can be achieved by a much simpler DFS. – Dennison

Citation: CLRS Introduction to Algorithms 3rd edition page 604-610. – Salmonoid

Answer 2

What you really need, I believe, is a topological sorting algorithm like the one described here:

http://en.wikipedia.org/wiki/Topological_sorting

If the directed graph has a cycle then the algorithm will fail.

The comments/replies that I've seen so far seem to be missing the fact that in a directed graph there may be more than one way to get from node X to node Y without there being any (directed) cycles in the graph.

Anglocatholic

Answer 3

Use DFS to search if any path is cyclic

class Node<T> { T value; List<Node<T>> adjacent;  }

class Graph<T>{

    List<Node<T>> nodes;

   public boolean isCyclicRec()
   {

      for (Node<T> node : nodes)
      {
            Set<Node<T>> initPath = new HashSet<>();
            if (isCyclicRec(node, initPath))
            {
              return true;
            }
      }
      return false;
   }

   private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path)
   {
      if (path.contains(currNode))
      {
        return true;
      }
      else
      {
        path.add(currNode);
        for (Node<T> node : currNode.adjacent)
        {
            if (isCyclicRec(node, path))
            {
                return true;
            }
            else
            {
                path.remove(node);
            }
        }
      }
      return false;
  }

Gassaway

You haven't defined the function isCyclic at all. – Prather

this code fails on this input: 4 -> 1->2->3. it fails if you start exploring from node 1. – Nace

found how to fix: Set<Node<T>> initPath = new HashSet<>(); should be inside for loop. – Nace

Answer 4

approach:1
how about a level no assignment to detect a cycle. eg: consider the graph below. A->(B,C) B->D D->(E,F) E,F->(G) E->D As you perform a DFS start assigning a level no to the node you visit (root A=0). level no of node = parent+1. So A=0, B=1, D=2, F=3, G=4 then, recursion reaches D, so E=3. Dont mark level for G (G already a level no assigned which is grater than E) Now E also has an edge to D. So levelization would say D should get a level no of 4. But D already has a "lower level" assigned to it of 2. Thus any time you attempt to assign a level number to a node while doing DFS that already has a lower level number set to it, you know the directed graph has a cycle..

approach2:
use 3 colors. white, gray, black. color only white nodes, white nodes to gray as you go down the DFS, color gray nodes to black when recursion unfolds (all children are processed). if not all children yet processed and you hit a gray node thats a cycle. eg: all white to begin in above direct graph. color A, B, D, F,G are colored white-gray. G is leaf so all children processed color it gray to black. recursion unfolds to F(all children processed) color it black. now you reach D, D has unprocessed children, so color E gray, G already colored black so dont go further down. E also has edge to D, so while still processing D (D still gray), you find an edge back to D(a gray node), a cycle is detected.

Espinosa

Answer 5

Testing for Topological sort over the given graph will lead you to the solution. If the algorithm for topsort, i.e the edges should always be directed in one way fails, then it means that the graph contains cycles.

Cureton

Answer 6

Another simple solution would be a mark-and-sweep approach. Basically, for each node in tree you flag it as "visited" and then move on to it's children. If you ever see a node with the "visted" flag set, you know there's a cycle.

If modifying the graph to include a "visited" bit isn't possible, a set of node pointers can be used instead. To flag a node as visited, you place a pointer to it in the set. If the pointer is already in the set, there's a cycle.

Lancaster

this solution is similar to the one provided by KennyTM, but it is better to the problem. The problem is to identify cycles, so mark-and-sweep is a good approach. Building the spanning tree, as suggested by KennyTM, is a more complex way to solve the problem, because you are using the concept of spanning tree. At the end, it is almost all the same. – Gammer

@Rakis: Will it misidentify en.wikipedia.org/wiki/File:Diamond_inheritance.svg as a cycle? – Functionalism

@KennyTM: Yes, it will. And it doesn't matter if you use DFS or BFS to explore the nodes in the graph - you will get the same incorrect answer either way. It's not enough to keep track of which nodes have been visited in order to identify cycles. So I would deduct a point for the answer by Rakis (but my reputation is too meager to do so). – Anglocatholic

Ah, indeed it would. I suppose I was thinking of a tree rather than an actual graph. However, I believe the same general approach would still work in that case by tracking visited edges rather than visted nodes. Using a set of (from_node_id, to_node_id) pairs would detect traversing the same edge more than once. – Lancaster

The correct solution contains mark-and-sweep, but requires three colors. You mark unvisited nodes white, nodes being visited gray, and nodes that root a completely visited sub-graph black. See personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/… – Salmonoid