GraphsLesson 34Free preview
DSA Cycle Detection
This lesson is part of DSA · All levels
Summary
Cycle detection checks for tracks that go back to the same node. On the non-directional graph, the cycle is detected when the DFS finds a neighbor that has already been visited other than its parent. The directional graph uses three status markers: unvisited, currently visited, and completed.
Key points
- Directionless graph: a cycle is when the edge to the visited node is outside the parent
- Directional graphs: using gray (white) and black (finished) markers
- Recursive DFS is the most common approach to cycle detection
- Useful for validation of dependencies and topological sort
Full lesson
Code examples and quizzes
Full lessons, code examples, and quizzes are available to subscribers. 5 questions.