How can we detect if a directed graph is cyclic? I thought using breadth first search, but I'm not sure. Any ideas?
+4
A:
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.
KennyTM
2010-03-26 17:25:37
BFS or DFS have the same complexity (runtime) and applicability (same result) on this problem. The only difference is in the visiting order of the nodes.
darlinton
2010-03-26 17:46:26
The last statement on the page indicated in the link is a topological statement based on the number of edges and vertices:"The maximum number of possible edges in the graph G if it does not have cycle is |V| - 1."This is true for *undirected* graphs, but not for *directed* graphs, as indicated in the original question. For directed graphs, the "diamond inheritance" diagram provides a counterexample (4 nodes and 4 edges make a "loop", but not a "cycle" that can be traversed by following the arrows).
Peter
2010-03-29 16:49:32
In case the last comment wasn't clear - I'm saying that the accepted answer is sufficient for undirected graphs, but *wrong* for directed graphs (as specified in the question).
Peter
2010-03-29 18:44:42
@Peter: The previous link maybe wrong, but the concept I've described is correct even for digraphs. I made the terminology clearer and provided a better source.
KennyTM
2010-03-29 18:54:20
@darlinton: but it is an overkill to do `BFS` because the same thing can be achieved by a much simpler `DFS`.
Lazer
2010-04-05 05:00:01
@eSKay: completely sure!
darlinton
2010-04-08 17:18:47
+2
A:
Another simple solution would be a mark-and-sweep approach. Basically, for each node in tree you flag it as "visited" and then move on to it's children. If you ever see a node with the "visted" flag set, you know there's a cycle.
If modifying the graph to include a "visited" bit isn't possible, a set of node pointers can be used instead. To flag a node as visited, you place a pointer to it in the set. If the pointer is already in the set, there's a cycle.
Rakis
2010-03-26 17:40:28
this solution is similar to the one provided by KennyTM, but it is better to the problem. The problem is to identify cycles, so mark-and-sweep is a good approach. Building the spanning tree, as suggested by KennyTM, is a more complex way to solve the problem, because you are using the concept of spanning tree. At the end, it is almost all the same.
darlinton
2010-03-26 17:48:56
@Rakis: Will it misidentify http://en.wikipedia.org/wiki/File:Diamond_inheritance.svg as a cycle?
KennyTM
2010-03-26 18:26:26
@KennyTM: Yes, it will. And it doesn't matter if you use DFS or BFS to explore the nodes in the graph - you will get the same incorrect answer either way. It's not enough to keep track of which nodes have been visited in order to identify cycles. So I would deduct a point for the answer by Rakis (but my reputation is too meager to do so).
Peter
2010-03-29 16:42:16
Ah, indeed it would. I suppose I was thinking of a tree rather than an actual graph. However, I believe the same general approach would still work in that case by tracking visited edges rather than visted nodes. Using a set of (from_node_id, to_node_id) pairs would detect traversing the same edge more than once.
Rakis
2010-04-01 14:15:03
+1
A:
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.
Peter
2010-03-29 17:11:22