algorithmgraph-theorydirected-graph

Efficient algorithm for detecting cycles in a directed graph

Is there an efficient algorithm for detecting cycles within a directed graph?

I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a dependency being an edge. I need to detect the error case of a cycle within this graph leading to cyclic dependencies.

It would be better to detect all cycles so they could be fixed in one go.

Solution

  • Tarjan's strongly connected components algorithm has O(|E| + |V|) time complexity.

    For other algorithms, see Strongly connected components on Wikipedia.