How to detect if a directed graph is cyclic?
algorithm, breadth-first-search, cyclic-graph, directed-graph, graph
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.
Problem
How can we detect if a directed graph is cyclic? I thought using breadth first search, but I'm not sure. Any ideas?