Detect Cycle in Undirected Graph (BFS)
Does an undirected graph contain a cycle? Detect it with BFS.
- 1 <= V <= 10⁵
- 0 <= E <= 10⁵
- Graph may be disconnected, so start BFS from every unvisited vertex
Intuition
To detect cycle in undirected graph bfs, the obvious rule — "if a neighbour is already visited, there is a cycle" — is wrong, and understanding why is the whole problem.
In an undirected graph, every edge can be walked in both directions. When you arrive at vertex v from vertex u, then look at v's neighbours, u is among them and is already visited. That is not a cycle; it is simply the edge you just crossed, seen from the other end.
So one exception has to be carved out:
- A visited neighbour that is the parent is just the edge you arrived on; a visited neighbour that is anything else means a second, independent path reached it — which closes a cycle.
That means the parent must travel with each vertex. In BFS, queue (vertex, parent) pairs so every dequeued vertex knows which edge brought it there.
One more detail matters: the graph may be disconnected, and a cycle can hide in any component. So the outer loop must restart BFS from every vertex not yet visited, rather than assuming one traversal reaches everything.
Worth noting that this parent trick does not transfer to directed graphs. There, an edge into an already-finished vertex is harmless, and detecting a cycle requires tracking which vertices are currently on the recursion stack instead.
Cycle detection in undirected graph bfs is the 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.
Approach
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(V + E) time and O(V) space.
See why plain visited-checking fails
Arriving at v from u means u is a visited neighbour of v. That is the edge you just used, not a cycle — and treating it as one reports a cycle on every graph with at least one edge.
Carry the parent in the queue
Enqueue (vertex, parent) pairs rather than bare vertices. Each dequeued vertex then knows which edge brought it there and can exclude exactly that one neighbour from the cycle test.
Test each visited neighbour against the parent
For a neighbour already visited, ignore it if it is the parent. If it is anything else, two distinct paths have reached it, which means a cycle — return true immediately without exploring further.
Mark on enqueue, not on dequeue
Set a vertex visited when it enters the queue. Marking at dequeue time lets the same vertex be enqueued twice from different neighbours, producing a false cycle report on a perfectly acyclic graph.
Restart at every unvisited vertex
The graph may have several components and a cycle can hide in any of them. A single BFS only covers the start vertex's component, so loop over all vertices and launch a traversal from each unvisited one.
Note that directed graphs need a different test
In a directed graph an edge into a finished vertex is legal, so the parent exception does not apply. That case needs recursion-stack tracking — the white/grey/black colouring — which is a genuinely different algorithm.
Cost of the traversal
Every vertex is enqueued once and every edge examined twice, once from each end, giving O(V + E) time. Space is O(V) for the visited array and the queue.
Solution & live demo
Common pitfalls
Queueing vertices without their parent
q = deque([s]) ... elif seen[u]: return True
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
v, parent = q.popleft() seen[v] = True
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
elif u != parent: return True # with parallel edges present
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.
Edge cases
Never finds a non-parent visited neighbour — no cycle.
Each component is checked separately.
The second edge looks like a non-parent revisit and is correctly reported as a cycle.