6

For undirected graphs , if we need to find a cycle , we use depth-first search as described in this older question,which is a well known method and also optimal .

But for directed graph, this other question suggests using topological sorting.

My question is, why can't we use the same technique we use for undirected graphs, to check for cycles in directed graph? I've thought of various cases and the algorithms always seem to agree.

Can anyone come up with some example directed graph where DFS fails to find a cycle but topological sorting does?

Community
  • 1
  • 1
Spandan
  • 2,128
  • 5
  • 25
  • 37
  • 1
    by the way topological sort is achieved by doing DFS (there may be other ways too). So consider both of them as same at least in this context. – Deep May 29 '13 at 12:29

1 Answers1

9

It seems like your question is the following: can you use depth-first search to detect cycles in an undirected graph, or should you use topological sort instead?

The answer is that both approaches will work. If there is a cycle in a directed graph, then you can detect this by running a depth-first search over the graph. As soon as you start the search from a node in the cycle, you are guaranteed to eventually discover the cycle.

It turns out that topological sorting and DFS are closely related in the following way: if you run a DFS in a graph and don't find a cycle, then the reverse order in which you marked each node as fully-explored will give a topological sort of the graph. In other words, the solution of "use topological sort" and the solution of "use DFS" can be thought of as extremely similar algorithms, since one way to implement topological sorting is with DFS.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Thanks! Thats' perfectly explained. – Spandan May 27 '13 at 20:06
  • Sorry on posting on old thread. But I have one confusion. Can we detect cycles by doing topological sort of graph ? I think the answer is no because even if we have some cycles in the graph, topological sorting would be possible if we do by dfs based approach. – Patel Parth Jul 05 '18 at 22:15
  • A directed graph that has a cycle can't be topologically sorted, since it's never possible to order the nodes such that each node comes before/after the other nodes leading into it. The DFS-based algorithm can actually detect this with some modifications - you just need to keep track of which nodes are currently being explored but haven't yet finished and to report an error if you try expanding one of those nodes out. – templatetypedef Jul 05 '18 at 22:43
  • A directed graph that has a cycle CAN be topologically sorted. You can compare the count of the **processed node** and the **total node**. If they are the same, there is no circle. Otherwise, there has a circle. – Alfred May 15 '21 at 04:29
  • @Alfred A topological ordering of a directed graph is one where each node appears after all the nodes that have edges into it. If there’s a cycle, there’s no way to do this. – templatetypedef May 15 '21 at 16:16
  • If there is no edge into the node, you should terminate the loop and compare the **processed node** and the **total node**. – Alfred May 17 '21 at 01:32