Pattern visualizer

Detect Cycle in Undirected Graph

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. 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?.

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

time O(V + E)space O(V)step 1 / 12

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

DFS stack

line 4

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap