Search code examples
algorithmgraphbreadth-first-searchdirected-graphcyclic-graph

How to detect if a directed graph is cyclic?

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

Solution

  • 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.