Breadth-First Search

Breadth-First Search (BFS)

BFS explores a graph level by level — all nodes at distance 1, then distance 2, and so on. It uses a queue (FIFO).

Graph: 0 — 1 — 3
       |
       2

BFS from 0: [0, 1, 2, 3]

Algorithm

from collections import deque

def bfs(graph, start):
    visited = []
    seen = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()   # FIFO
        visited.append(node)
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb)     # mark before enqueuing!
                queue.append(nb)
    return visited

Key: mark nodes as seen when enqueuing, not when visiting. This prevents duplicates in the queue.

Properties

Applications

• Shortest path in unweighted graphs
• Level-order traversal of trees
• Finding connected components
• Web crawlers, social network analysis

Your Task

Implement bfs(graph, start) that returns a list of all reachable nodes in BFS order.