DFS/BFS/Topological sort/Graph Cycyle Finding
As you may know, we have two approach to solve the topological sort based on DAG:
- BFS
- DFS
What if we have cycles in the directed graph? Suppose this is course scheduling problem, we can easily using the BFS approach by counting how many courses have the zero indegree after you finishing the checking. When the number of courses is not equal to the total number of courses, it means we find a cycle.
Can we use DFS to detect cycls in a directed graph? We may can (Have to double confirm).
From [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. From [1]
