GeeksforGeeks Medium

Detect Cycle in Undirected Graph (BFS)

Does an undirected graph contain a cycle? Detect it with BFS.

graphbfscycle

02

Intuition

💡

In an undirected graph every edge can be walked back the way you came, so 'neighbour already visited' is not enough to prove a cycle — it might just be your parent. Carry the parent along in the queue: an already-visited neighbour that is not the parent means a second, independent path reached it, which closes a loop.

03

Approach

1

The parent exception

Queue (vertex, parent) pairs. When examining a neighbour that is already visited, ignore it if it is the parent — that is only the edge you arrived on.

2

Any other visited neighbour is a cycle

If a visited neighbour is not the parent, two distinct paths reach it, so the graph has a cycle. Return immediately.

3

Repeat per component

A cycle may hide in any component, so restart BFS at each unvisited vertex.

04

Solution & live demo

python

▶1from collections import deque
▶2 
▶3def has_cycle_undirected_bfs(n, adj):
▶4    seen = [False] * n
▶5    for s in range(n):
▶6        if seen[s]: continue
▶7        seen[s] = True
▶8        q = deque([(s, -1)])      # (vertex, parent)
▶9        while q:
▶10            v, parent = q.popleft()
▶11            for u in adj[v]:
▶12                if not seen[u]:
▶13                    seen[u] = True
▶14                    q.append((u, v))
▶15                elif u != parent:  # visited and not where we came from
▶16                    return True
▶17    return False

05

Edge cases

Tree (V−1 edges, connected)

Never finds a non-parent visited neighbour — no cycle.

Disconnected graph

Each component is checked separately.

Parallel edges u–v twice

The second edge looks like a non-parent revisit and is correctly reported as a cycle.

06

Complexity

Time

O(V + E)

Space

O(V)

Standard BFS with one extra field per queue entry.