👋 Welcome Gophers! In this lesson, we are going to be covering Breadth-First Search (BFS) and how it works conceptually.
Overview
If DFS is like going deep into a maze, BFS is like exploring a maze level by level. Breadth-First Search explores all nodes at the current depth before moving to the next depth level. It’s perfect when you want to find the shortest path or explore neighbors before going deeper.
BFS uses a queue (FIFO - First In, First Out) to manage which nodes to visit next, making it fundamentally different from DFS.
How It Works
Here’s the step-by-step process:
- Start at your source node and add it to a queue
- Mark it as visited
- While the queue isn’t empty:
- Remove the front node from the queue
- For each unvisited neighbor, mark it as visited and add it to the queue
- Continue until the queue is empty
This level-by-level approach ensures we explore all nodes at distance 1 before moving to distance 2, and so on.
BFS vs DFS
Let’s compare these two fundamental algorithms:
| Aspect | DFS | BFS |
|---|---|---|
| Data Structure | Stack | Queue |
| Order | Deep then backtrack | Level by level |
| Memory | O(height) | O(width) |
| Use Cases | Topological sort, cycles | Shortest path, levels |
| Exploration | Exhaustive on one branch | Systematic across levels |
Time and Space Complexity
- Time Complexity: O(V + E) where V is vertices and E is edges. Same as DFS—we visit every node and edge once.
- Space Complexity: O(V) for the queue. On a wide graph, the queue can get quite large!
Visual Example
Here’s how BFS explores a graph level by level:
<svg viewBox="0 0 600 380" xmlns="http://www.w3.org/2000/svg">
<!-- Background -->
<rect width="600" height="380" fill="#1a1a2e"/>
<!-- Title -->
<text x="300" y="30" text-anchor="middle" fill="#00d9ff" font-size="18" font-weight="bold">
Breadth-First Search Level-by-Level
</text>
<!-- Level indicators -->
<text x="50" y="70" fill="#888" font-size="11" font-weight="bold">Level 0:</text>
<text x="50" y="160" fill="#888" font-size="11" font-weight="bold">Level 1:</text>
<text x="50" y="250" fill="#888" font-size="11" font-weight="bold">Level 2:</text>
<text x="50" y="320" fill="#888" font-size="11" font-weight="bold">Level 3:</text>
<!-- Start node (Node 0) - Red -->
<circle cx="150" cy="60" r="25" fill="#ff6b6b" stroke="#00d9ff" stroke-width="2"/>
<text x="150" y="67" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">0</text>
<!-- Level 1 nodes -->
<circle cx="100" cy="150" r="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
<text x="100" y="157" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">1</text>
<circle cx="200" cy="150" r="25" fill="#4ecdc4" stroke="#00d9ff" stroke-width="2"/>
<text x="200" y="157" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">2</text>
<!-- Level 2 nodes -->
<circle cx="75" cy="240" r="25" fill="#45b7aa" stroke="#00d9ff" stroke-width="2"/>
<text x="75" y="247" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">3</text>
<circle cx="150" cy="240" r="25" fill="#45b7aa" stroke="#00d9ff" stroke-width="2"/>
<text x="150" y="247" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">4</text>
<circle cx="225" cy="240" r="25" fill="#45b7aa" stroke="#00d9ff" stroke-width="2"/>
<text x="225" y="247" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">5</text>
<!-- Level 3 nodes -->
<circle cx="150" cy="310" r="25" fill="#95e1d3" stroke="#00d9ff" stroke-width="2"/>
<text x="150" y="317" text-anchor="middle" fill="#fff" font-size="14" font-weight="bold">6</text>
<!-- Edges -->
<defs>
<marker id="arrowhead" markerWidth="10" markerHeight="10" refX="9" refY="3" orient="auto">
<polygon points="0 0, 10 3, 0 6" fill="#666"/>
</marker>
</defs>
<!-- 0 -> 1 and 0 -> 2 -->
<line x1="133" y1="82" x2="110" y2="125" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>
<line x1="167" y1="82" x2="190" y2="125" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>
<!-- 1 -> 3 and 1 -> 4 -->
<line x1="90" y1="172" x2="80" y2="215" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>
<line x1="110" y1="172" x2="140" y2="215" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>
<!-- 2 -> 4 and 2 -> 5 -->
<line x1="190" y1="172" x2="160" y2="215" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>
<line x1="210" y1="172" x2="235" y2="215" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>
<!-- 4 -> 6 -->
<line x1="150" y1="265" x2="150" y2="335" stroke="#666" stroke-width="2" marker-end="url(#arrowhead)"/>
<!-- Queue order -->
<text x="320" y="100" fill="#00d9ff" font-size="13" font-weight="bold">Queue Order:</text>
<text x="320" y="130" fill="#a8dadc" font-size="12">1. Process 0</text>
<text x="320" y="155" fill="#a8dadc" font-size="12">2. Process 1, 2 (neighbors of 0)</text>
<text x="320" y="180" fill="#a8dadc" font-size="12">3. Process 3, 4, 5 (neighbors of 1, 2)</text>
<text x="320" y="205" fill="#a8dadc" font-size="12">4. Process 6 (neighbor of 4)</text>
<text x="320" y="260" fill="#888" font-size="11">Red = Start | Teal = Early | Light = Later</text>
</svg>
Notice how we process all nodes at one level before moving to the next: Level 0 (node 0) → Level 1 (nodes 1, 2) → Level 2 (nodes 3, 4, 5) → Level 3 (node 6).
When to Use BFS
BFS is ideal for:
- Finding shortest paths in unweighted graphs
- Finding the shortest distance between two nodes
- Level-order traversal of trees
- Finding connected components
- Social network analysis (friends of friends at each level)
- Puzzle solving where you need to explore all possibilities at each distance
Quiz Time
Validate what you’ve learned in this lesson by attempting these quiz questions: