Breadth-first search
Explore a graph one distance layer at a time. A queue keeps earlier discoveries ahead of later discoveries.
Trace a connected component
Mark a vertex discovered when you enqueue it. Two parents may share a neighbor; this rule prevents duplicate work.
Undirected edges: A–B, A–C, B–D, C–D. Visit neighbors alphabetically. Start at A.
Step 1 of 5: Enqueue A.
Queue: A
Discovered: A
Read the complete trace
- Enqueue A. Queue: A.
- Process A. Discover each unseen neighbor once. Queue: B, C.
- Process B. Discover each unseen neighbor once. Queue: C, D.
- Process C. Discover each unseen neighbor once. Queue: D.
- Process D. Discover each unseen neighbor once. Queue: empty.
Invariant and complexity
The queue contains discovered vertices waiting to be processed. With adjacency lists, visiting the reachable component takes O(V + E) time and O(V) auxiliary space. Use a queue with constant-time removal, or an array with a head index.
Try it yourself
Add an isolated vertex E. Starting at A will not reach it. To visit every component, start another traversal from an undiscovered vertex.
Practise a graph problem →