BFS

Worked by hand

The same graph, traced by hand

Edges: A–B, A–C, B–D, B–E, C–F, E–F. Start at A. At each step the queue is shown after processing.

take out	new neighbours (distance)	queue afterwards
A	B (1), C (1)	B, C
B	D (2), E (2) (A already seen)	C, D, E
C	F (2) (A already seen)	D, E, F
D	none new	E, F
E	none new (B, F seen)	F
F	none new	empty

1
Distances come out in rings
A is 0; B, C are 1; D, E, F are 2. The order nodes leave the queue (A, B, C, D, E, F) is also sorted by distance.
2
F was reached from C, not E
Both C and E are neighbours of F. C left the queue first, so C discovered F. That is why the shortest path to F is A, C, F (2 edges).

Implementation

Distances from a start node

Keep one dictionary that plays two roles: its keys are the nodes already seen, and its values are their distances.

Plan in plain steps

pseudocode

dist[start] = 0; queue = [start]
while queue is not empty:
    u = remove from the front
    for each neighbour v of u:
        if v has no distance yet:
            dist[v] = dist[u] + 1
            add v to the back

python

from collections import deque

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

def bfs(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

print(bfs(graph, "A"))   # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

Reading the code

›deque (from collections) gives O(1) removal from the front with popleft(). A plain list's pop(0) shifts every element and is O(n), which would quietly make BFS slow.
›if v not in dist is the “never revisit” rule. We write the distance at the moment we *add* v, not when we remove it, so v cannot be added twice.
›dist[u] + 1: a neighbour is one edge further than the node that discovered it.
›Nodes unreachable from start never appear in dist. Use dist.get(x, -1) when you need “unreachable” as a value.

Implementation

Recovering the actual path

Distances say how far; often you need the route too. Remember *who discovered* each node (its parent), then walk the parents backwards from the target.

python

from collections import deque

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

def shortest_route(graph, s, t):
    parent = {s: None}
    q = deque([s])
    while q:
        u = q.popleft()
        if u == t:
            break
        for v in graph[u]:
            if v not in parent:
                parent[v] = u
                q.append(v)
    if t not in parent:
        return None
    path = []
    while t is not None:
        path.append(t)
        t = parent[t]
    return path[::-1]

print(shortest_route(graph, "A", "F"))   # ['A', 'C', 'F']

Reading the code

›parent replaces dist as the seen-set. The start has parent None, which marks where to stop walking back.
›We stop early with break once the target is taken from the queue: nothing later can be closer.
›The walk back produces the route in reverse (target to start), so path[::-1] flips it.

Implementation

BFS on a grid

For a maze, each cell is a node and its neighbours are the open cells up, down, left and right. The queue holds (row, column) pairs. There is no stored graph: we compute neighbours on the fly.

python

from collections import deque

def shortest_path(grid, start, goal):
    R, C = len(grid), len(grid[0])
    dist = {start: 0}
    q = deque([start])
    while q:
        r, c = q.popleft()
        if (r, c) == goal:
            return dist[(r, c)]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "." and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return -1

grid = ["..#.",
        "..#.",
        "....",
        "#..."]
print(shortest_path(grid, (0, 0), (0, 3)))   # 7

Reading the code

›The four pairs in the for are the moves down, up, right, left. Add four more for diagonals if the problem allows them.
›The bounds check 0 <= nr < R and 0 <= nc < C must come before grid[nr][nc]; otherwise a negative index silently wraps around in Python.
›The wall at column 2 forces the route down to row 2, across, then back up: 7 moves.
›-1 means the goal is unreachable.

Worked problem

Distance to the nearest zero

The problem

Given a matrix of 0s and 1s, return a matrix where each cell holds the distance (in up/down/left/right moves) to the nearest 0. Assume at least one 0 exists.

Running BFS from every 1 would be slow (one search per cell).
Flip it around: start from all zeros at once. Put every 0 in the queue with distance 0, then run one BFS. The ripples spread from all zeros simultaneously, so each cell is first reached from its nearest zero.
This is multi-source BFS: the only change from normal BFS is that the queue starts with many nodes.

python

from collections import deque

def nearest_zero(mat):
    R, C = len(mat), len(mat[0])
    dist = [[-1] * C for _ in range(R)]
    q = deque()
    for r in range(R):
        for c in range(C):
            if mat[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

print(nearest_zero([[0, 0, 0], [0, 1, 0], [1, 1, 1]]))   # [[0, 0, 0], [0, 1, 0], [1, 2, 1]]

Takeaway. “Nearest of many things” means multi-source BFS: seed the queue with all sources. One O(R × C) search replaces R × C separate searches.

Worked problem

Shortest route between two nodes

The problem

In an unweighted undirected graph, print one shortest route from s to t, or report that none exists.

Run BFS from s and record each node's parent.
Stop when t is reached.
Walk the parents from t back to s and reverse.

python

from collections import deque

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

def route(graph, s, t):
    parent = {s: None}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in parent:
                parent[v] = u
                q.append(v)
    if t not in parent:
        return None
    out = []
    while t is not None:
        out.append(t)
        t = parent[t]
    return out[::-1]

print(route(graph, "D", "F"))   # ['D', 'B', 'E', 'F']
print(len(route(graph, "D", "F")) - 1)   # 3

Takeaway. Distance tells you how far; parents tell you how. Storing the parent costs nothing extra and turns a length into a route.

Wrap-up

Remember this

BFS explores a graph in rings of increasing distance, so the first arrival at a node is by a shortest route.
A queue (first in, first out) produces that order; mark nodes seen when you add them.
It costs O(V + E) because each node enters the queue once and each edge is scanned a constant number of times.
Store parents to rebuild the path; seed the queue with every source for “nearest” problems.
It is only correct for unweighted shortest paths. Weighted graphs need Dijkstra.

Cheat sheet

Template: queue; mark seen on add; dist[v] = dist[u] + 1
Queue type: collections.deque, popleft()
Cost: O(V + E); grid O(R × C)
Answers: fewest edges in an unweighted graph
Path: store parent[v] = u, walk back from target
Many sources: put all sources in the queue first (multi-source BFS)

Top traps to avoid

Marking a node as seen when you remove it from the queue, not when you add it.
Using list.pop(0) as a queue.
Checking the grid cell before checking bounds.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why does BFS find shortest paths in an unweighted graph?
2.In the lesson's graph, what is the BFS distance from A to E?
3.What is BFS's time complexity on a graph with V nodes and E edges stored as adjacency lists?
4.When should you mark a node as seen?
5.“Find the distance from every cell to its nearest exit” suggests:
6.Why is collections.deque preferred over a list for the queue?
7.Graph {1:[2,3], 2:[4], 3:[4], 4:[]}. What does BFS from node 1 visit, in order?
8.Undirected edges (1,2),(2,3),(3,5),(1,4),(4,5). What is the fewest edges on a path from 1 to 5?
9.Multi-source BFS: sources are nodes 1 and 5 on the path 1-2-3-4-5. What is the distance from each node 1 to 5 to its nearest source?
10.Grid rows '..#', '..#', '#..' with '.' open and '#' blocked. Starting at the top-left, how many open cells can BFS reach (4-directional moves)?
11.Why does BFS give shortest paths in an unweighted graph?
12.What is the running time of BFS on a graph with n nodes and m edges?
13.What must BFS record to avoid looping forever on a cyclic graph?
14.Which data structure does BFS use?
15.When is DFS (depth-first) a better choice than BFS for finding a path?

After this lesson you will be able to

Builds on

Unlocks

A stone dropped in a pond

Graphs in one minute

Why not just try every route?

Explore by distance, and never revisit

BFS on a six-node graph

The same graph, traced by hand

Distances from a start node

Reading the code

Recovering the actual path

Reading the code

BFS on a grid

Reading the code

Why O(V + E)

Edge cases

Mistakes to avoid

How to spot a BFS problem

Distance to the nearest zero

Shortest route between two nodes

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core6 problems

Application5 problems

Challenge2 problems