[FIXED] How to detect if a directed graph is cyclic?

Issue

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.

Answered By - kennytm

Answer Checked By - Pedro (PHPFixing Volunteer)