Algorithms and Data Structures · Middle · Question 33 of 75
How do you detect a cycle in a directed graph with DFS?
- 1Any edge to an already visited vertex means a cycle
- 2A cycle exists if any vertex has more than one outgoing edge
- ✓Correct answer: Track the current DFS path; an edge back into it is a cycle
Explanation
Use three states: unvisited, in progress (on the stack) and done. Only an edge to an "in progress" vertex is a back edge. An edge to a "done" vertex is fine: it's just another path to the same place.