BFS on Trees

BFS explores a graph layer by layer—first visit is shortest hop count in unweighted graphs.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Queue FIFO: pop front, push unvisited neighbors. Track dist or parent arrays. On grids, encode cell (r,c) as one node.

Try this in Python

from collections import deque


def bfs_shortest(adj: list[list[int]], start: int) -> list[int]:
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist


print(bfs_shortest([[1, 2], [0], [0]], 0))

Common mistakes

• Using BFS on weighted graphs (need Dijkstra).
• Forgetting visited set → infinite queue loops.

Key takeaways

• Multi-source BFS: enqueue all sources at dist 0.
• 0-1 weights: deque Dijkstra (multi-state lesson).