Cycle Detection
Undirected: an edge to a seen vertex other than the parent. Directed: an edge to a vertex still on the DFS path.
Decision · step 2 of 8DFS Checks: An undirected cycle
At 0, edge to 1. 1 is unseen, so enter it with parent 0.
What you will see
Vertices on the current path are marked; an edge that lands on one of them is the cycle.
Cost
| Best | O(V + E) |
|---|---|
| Average | O(V + E) |
| Worst | O(V + E) |
| Space | O(V) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Vertices announce name, neighbours and state (in queue, visited, current); each step announces which vertex is processed and which neighbours are discovered.
Reduced motion: Frontier and visited changes are crossfades; the traversal edge is emphasized without a travelling token.
Before this
Variants
- Undirected (DFS or Union-Find) Back edge to a non-parent.
- Directed (DFS colours) Grey-to-grey edge.