BFS Algorithm Structure
What You'll Learn
You'll learn how Breadth-First Search uses a queue to systematically explore a graph level by level, ensuring every vertex at distance k is visited before any vertex at distance k+1.
The Core Mechanism
BFS explores a graph like ripples spreading across water. Starting from a source vertex, it visits all immediate neighbors first, then neighbors of neighbors, and so on—always moving outward in layers.
The algorithm relies on three key components:
1. Queue for Frontier Management
BFS uses a queue (FIFO: First-In-First-Out) to track which vertices to visit next. You enqueue the starting vertex, then repeatedly:
- Dequeue the front vertex
- Process it
- Enqueue all its unvisited neighbors
This FIFO ordering guarantees level-by-level traversal.
2. Visited Marking
To avoid revisiting vertices (and infinite loops in cyclic graphs), BFS marks each vertex as "visited" the moment it's enqueued—not when it's dequeued. This prevents the same vertex from being added multiple times.
3. Systematic Neighbor Processing
For each dequeued vertex, BFS examines all its neighbors. Any unvisited neighbor gets marked and enqueued. This ensures complete coverage of the graph.
The Pattern
- Initialize: Mark source as visited, enqueue it
- While queue is not empty:
- Dequeue a vertex
- For each unvisited neighbor:
- Mark it visited
- Enqueue it
This structure naturally produces a shortest-path tree in unweighted graphs, since the first time you reach any vertex, you've taken the fewest edges possible.
Key Takeaway: BFS uses a queue to visit vertices level by level, marking nodes visited when enqueued and systematically processing all neighbors to ensure complete, orderly graph exploration.