Enqueue every unseen start, repeatedly dequeue a vertex and discover its unseen neighbors, and scan all vertices outside the search to partition G.
Recognition signals
The core task is graph or implicit-state traversal, not weighted optimization.
Avoiding recursive depth is important.
Near-to-far expansion order is useful for observation or later extension.
Parents, levels, or component IDs should be recorded at discovery time.
False friends
Signal
Why it is different
Unequal-weight shortest path
FIFO does not order total cost; use Dijkstra or 0-1 BFS.
Topological layers
A dependency layer is governed by remaining indegree, not geometric distance from an arbitrary source.
Core invariant
Every queued vertex is discovered and assigned to the current component but not fully expanded; an unseen vertex is not yet proven reachable from this start.
State, transition, and processing order
Item
Definition
State
FIFO queue, visited set, component ID, and optional parent or level maps.
Transition
Dequeue u; immediately mark and enqueue each eligible unseen neighbor v.
Frontier / order
A FIFO queue preserving discovery order, so one layer is expanded before the next.
Python skeleton
from collections import deque
def bfs_groups(graph):
seen, label = set(), {}
group_id = 0
for start in graph:
if start in seen:
continue
seen.add(start)
q = deque([start])
while q:
u = q.popleft()
label[u] = group_id
for v in graph[u]:
if v not in seen:
seen.add(v)
q.append(v)
group_id += 1
return group_id, label
Correctness sketch
Each enqueue follows an actual edge from an already reachable vertex, so no foreign component is admitted.
Induction along any path proves that every reachable vertex is eventually discovered.
Discovery-time marking assigns each vertex once; the outer scan starts all remaining components.
Complexity
Time
Space
Parameters
O(V+E)
O(V)
V is the vertex count and E the total adjacency size; the queue can be as wide as V.
Edge cases
A single vertex is one component.
Each isolated vertex needs an outer-loop launch.
Parallel adjacency entries must not create duplicate enqueues.
Include vertices that appear only as edge destinations.
Error patterns
Pattern
Why it fails / fix
Using list.pop(0)
Element shifting makes dequeue linear; use deque.popleft.
Marking after dequeue
A diamond can enqueue the same vertex multiple times.
Generalizing first discovery to all weights
Only equal-cost edges make a BFS layer equal minimum cost.
Selection and exclusion rules
Default to BFS for component traversal when recursion depth is uncertain.
Add a distance field to upgrade the skeleton to unweighted shortest path.
For static components BFS and DFS have equal asymptotics; choose the clearer state model.