Breadth-First Search

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 1 Time to complete: ~25 minutes

Table of Contents

1. BFS: Explore Layer by Layer
2. Why You Need a Visited Set
3. BFS Implementation
4. Worked Trace
5. Shortest Path in an Unweighted Graph
6. Complexity
7. Summary & Next Steps

1. BFS: Explore Layer by Layer

Breadth-first search (BFS) starts at a node and explores all of its immediate neighbors first, then all of their neighbors, and so on — expanding outward in concentric "layers." You already saw this exact idea in Module 7 Chapter 2's level-order tree traversal — BFS on a graph is that same algorithm, generalized beyond trees.

The tool that makes this work is the queue from Module 5: a FIFO structure guarantees that nodes are processed in the order they were discovered, which is exactly what "layer by layer" requires.

2. Why You Need a Visited Set

Trees have no cycles, so Module 7's traversals never risked revisiting a node. Graphs can have cycles — without tracking which nodes you've already seen, BFS could loop forever bouncing between connected nodes. This is where Module 8's sets come back in directly: a visited set gives O(1) average-case membership checks, so marking and checking "have I seen this node" doesn't itself become a bottleneck.

    A --- B
    |     |
    C --- D      ← a cycle exists: A-B-D-C-A

Without a visited set, BFS starting at A could traverse A → B → D → C → A → B → ... indefinitely.

3. BFS Implementation

from collections import deque
 
def bfs(graph, start):
    visited = {start}              # mark as visited THE MOMENT it's added to the queue
    queue = deque([start])
    order = []
 
    while queue:
        node = queue.popleft()      # O(1) — Module 5's deque, not list.pop(0)
        order.append(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:      # O(1) average — Module 8's sets
                visited.add(neighbor)
                queue.append(neighbor)
 
    return order

Critical detail: mark a node as visited when you add it to the queue, not when you pop it. If you wait until popping, the same node can be queued multiple times by different neighbors before it's ever processed, wasting work and — in graphs with certain shapes — causing incorrect results.

4. Worked Trace

Using the graph from Chapter 1:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}
 
print(bfs(graph, "A"))

Step 1: visit A, queue neighbors B, C           → visited={A,B,C}, queue=[B,C]
Step 2: pop B, queue new neighbor D              → visited={A,B,C,D}, queue=[C,D]
Step 3: pop C, D already visited, nothing new    → queue=[D]
Step 4: pop D, queue new neighbor E              → visited={A,B,C,D,E}, queue=[E]
Step 5: pop E, no new neighbors                  → queue=[]

Order: A, B, C, D, E

Notice the layer structure: A (layer 0), then B, C (layer 1, both distance 1 from A), then D (layer 2), then E (layer 3).

5. Shortest Path in an Unweighted Graph

Because BFS visits nodes in increasing order of distance from the start, the first time you reach any node is via a shortest path to it — this is BFS's single most important practical use case.

from collections import deque
 
def shortest_path_length(graph, start, end):
    if start == end:
        return 0
 
    visited = {start}
    queue = deque([(start, 0)])      # (node, distance from start)
 
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
 
    return -1     # end is unreachable from start
 
print(shortest_path_length(graph, "A", "E"))     # 3 → A-B-D-E or A-C-D-E

6. Complexity

Time: O(V + E) — every vertex is visited once (O(V)), and every edge is examined once when scanning neighbor lists (O(E)). Space: O(V) — the visited set and queue can each hold up to all vertices in the worst case.

7. Summary & Next Steps

Key Takeaways

• BFS explores a graph layer by layer using a queue (Module 5), mirroring Module 7's level-order tree traversal generalized to graphs.
• A visited set (Module 8) is required to avoid infinite loops on cyclic graphs — mark nodes visited when enqueued, not when dequeued.
• BFS's signature use case is shortest path in an unweighted graph — the first visit to any node is guaranteed to be via the fewest possible edges.
• Time and space complexity are both O(V + E) / O(V) — linear in the size of the graph.

Concept Check

1. Why does BFS use a queue instead of a stack?
2. What goes wrong if you mark a node as visited only when it's popped from the queue, rather than when it's added?
3. Why does the first time BFS reaches a node guarantee that path is a shortest path?

Next Chapter

→ Chapter 3: Depth-First Search

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index