Why use DFS to find cycles in an undirected graph and topological sorting to find cycles in a directed graph?

Question

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?

Penninite

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. – Import

Answer 1

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!

Mattiematting

Thanks! Thats' perfectly explained. – Penninite

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. – Tasteful

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. – Mattiematting

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. – Morris

@Morris 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. – Mattiematting

If there is no edge into the node, you should terminate the loop and compare the processed node and the total node. – Morris