How to detect if a directed graph is cyclic?

iva123 picture iva123 · Mar 26, 2010 · Viewed 36.9k times · Source

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

Answer

Peter picture Peter · Mar 29, 2010

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.