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?

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!