Undirected Graph Cycle

DFS with parent tracking: a visited neighbour that isn't your parent is a cycle

time O(V + E)space O(V)

In an undirected graph every edge is two-way, so a DFS walking from a vertex back to the one it just came from is not a cycle — it's just turning around. The trick is to track, for each vertex, WHICH neighbour is its parent in the DFS. Any other already-visited neighbour means a second path reaches that vertex, which is exactly what a cycle is. One component can finish clean while another closes a loop, so the search has to try every unvisited vertex as a fresh root, not stop after the first one.

Details

Animated on: 7 vertices, undirected edges 0-1, 1-2 (a tree) and 3-4, 4-5, 5-6, 6-3 (a ring) — does this graph contain a cycle?

Problem:Undirected Graph CycleMedium

DFS with parent tracking: a visited neighbour that isn't your parent is a cycle

step 1 / 12

Badge = parent this vertex was reached from (- = component root)

DFS stack

0 starts a new component. Mark it visited with no parent — anything this DFS later finds already-visited outside of a parent link means two paths reach the same vertex, i.e. a cycle.

Pseudocode

1FUNCTION hasCycle(n, adj):
2  visited <- ARRAY OF n FALSE
3  FOR v FROM 0 TO n - 1
4    IF NOT visited[v] AND DFS(v, -1)
5      RETURN true
6  RETURN false
7FUNCTION DFS(u, parent):
8  visited[u] <- true
9  FOR EACH w IN adj[u]
10    IF visited[w] AND w != parent
11      RETURN true
12    IF NOT visited[w] AND DFS(w, u)
13      RETURN true
14  RETURN false

← / → step · space play · Home restart

Every step in words

Show all 12 steps

0 starts a new component. Mark it visited with no parent — anything this DFS later finds already-visited outside of a parent link means two paths reach the same vertex, i.e. a cycle.
Step into 1 from 0. Mark it visited and remember 0 as its parent — 0 is the ONE already-visited neighbour 1 is allowed to see without that counting as a cycle.
Step into 2 from 1. Mark it visited and remember 1 as its parent — 1 is the ONE already-visited neighbour 2 is allowed to see without that counting as a cycle.
2 has no unvisited neighbours left and none of its visited neighbours were anything but its parent, so backtrack.
1 has no unvisited neighbours left and none of its visited neighbours were anything but its parent, so backtrack.
0 has no unvisited neighbours left and none of its visited neighbours were anything but its parent, so backtrack — component {0, 1, 2} finished with no cycle.
3 starts a new component. Mark it visited with no parent — anything this DFS later finds already-visited outside of a parent link means two paths reach the same vertex, i.e. a cycle.
Step into 4 from 3. Mark it visited and remember 3 as its parent — 3 is the ONE already-visited neighbour 4 is allowed to see without that counting as a cycle.
Step into 5 from 4. Mark it visited and remember 4 as its parent — 4 is the ONE already-visited neighbour 5 is allowed to see without that counting as a cycle.
Step into 6 from 5. Mark it visited and remember 5 as its parent — 5 is the ONE already-visited neighbour 6 is allowed to see without that counting as a cycle.
From 6, the edge to 3 lands on a vertex that is already visited and is NOT 6's parent (5). That is a second way to reach 3, so RETURN true.
The back edge from 6 to 3 closes the loop 3-4-5-6-3 — four vertices connected in a ring with no dangling end. hasCycle RETURNS true.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Undirected Graph Cycle in the editor All Graph problems Back to roadmap