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.

How to spot this pattern

The BFS counterpart to the DFS parent trick: carry each vertex's parent through the queue, and any already-seen neighbour that isn't the parent is a back edge. Storing (vertex, parent) pairs is the whole adaptation — BFS has no call stack to inspect, so the provenance rides along with the data.

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

▶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

Common pitfalls

Queueing vertices without their parent

✗ Wrong

q = deque([s])
...
elif seen[u]: return True

✓ Right

q = deque([(s, -1)])
...
elif u != parent: return True

Every undirected edge appears in both adjacency lists, so the vertex you came from is always already visited — without the parent you report a cycle on a single edge. BFS can't inspect the call stack, so the parent must travel in the queue.

Marking visited at dequeue time

✗ Wrong

v, parent = q.popleft()
seen[v] = True

✓ Right

if not seen[u]:
    seen[u] = True
    q.append((u, v))

Two vertices can enqueue the same neighbour before either dequeues it, and the second arrival then looks like a back edge — a false cycle on a perfectly acyclic tree. Marking at enqueue time makes each vertex enter exactly once.

Excluding the parent by identity rather than per-edge

✗ Wrong

elif u != parent: return True   # with parallel edges present

✓ Right

elif u != parent: return True   # correct for simple graphs

Worth knowing the limit: this test assumes no duplicate edges between the same pair. Two parallel edges are a cycle, but both look like the parent and get excused. For multigraphs you must track edge identity, not vertex identity.

06

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.

07

Complexity

Time

O(V + E)

Space

O(V)

Standard BFS with one extra field per queue entry.