Skip to content

BFS (Breadth-First Search)

In one sentence

Breadth-first search explores in rings: first everything 1 step away, then everything 2 steps away, and so on. The rings can start from one vertex, or from many at once.

1. What problem does it solve?

Example — 1593E · Gardener and Tree (5-Graph · H, rating 1600)

A tree has \(n\) vertices. One operation removes all current leaves at once (a leaf is a vertex with at most one neighbour; a single vertex counts as a leaf). After \(k\) operations, how many vertices remain?

Limits: \(t \le 10^4\), \(n \le 4 \cdot 10^5\) (sum over tests), \(k \le 2 \cdot 10^5\). Each test case is preceded by an empty line.

Input          Output
6

14 1
1 2            7
... (12 more edges)

2 200000
1 2            0

3 2
1 2            0
2 3

5 1
5 1            3
3 2
2 1
5 4

6 2
5 1            1
2 5
5 6
4 2
3 4

7 1
4 3            2
5 1
1 3
6 1
1 7
2 1

Simulating is too slow. Each operation scans the whole tree, and \(k\) can be \(2 \cdot 10^5\).

Better question: in which round is each vertex removed? Call that its layer. Then the answer is simply the number of vertices with layer \(> k\).

The fourth test is a path \(4 - 5 - 1 - 2 - 3\):

graph LR
  4((4)) --- 5((5)) --- 1((1)) --- 2((2)) --- 3((3))
vertex 4 3 5 2 1
layer (round removed) 1 1 2 2 3

With \(k = 1\), the vertices with layer \(> 1\) are \(5, 2, 1\): 3 remain. ✓

2. How BFS works

2.1 Layers

Put the start in a queue with layer \(0\) (or \(1\)). Repeatedly take the oldest vertex out of the queue, and push each newly reached neighbour with layer \(+1\).

For Gardener and Tree the rings start from all leaves at once (layer \(1\)). This is multi-source BFS. When a vertex is removed, each neighbour loses one edge; the moment a neighbour has only one edge left, it becomes a leaf of the next round and joins the queue with layer \(+1\).

Trace on the seventh test (edges 4-3, 5-1, 1-3, 6-1, 1-7, 2-1): vertex \(1\) touches \(5, 3, 6, 7, 2\), and \(3\) also touches \(4\).

pop layer neighbours: degree after removing pushed
start leaves \(2, 4, 5, 6, 7\) 2 4 5 6 7, layer 1
2 1 1: \(5 \to 4\)
4 1 3: \(2 \to 1\) 3, layer 2
5 1 1: \(4 \to 3\)
6 1 1: \(3 \to 2\)
7 1 1: \(2 \to 1\) 1, layer 2
3 2 1: \(1 \to 0\)
1 2 —

With \(k = 1\): vertices \(3\) and \(1\) have layer \(2 > 1\). 2 remain. ✓

2.2 Why the queue processes rounds in order

Claim 1. The queue always holds layers in non-decreasing order, differing by at most \(1\): it looks like d d d … d+1 d+1.

Why: we pop a layer-\(d\) vertex from the front and push layer-\((d + 1)\) vertices to the back. If the queue was d … d+1 before, it is still of that shape after.

Claim 2. A vertex's BFS layer equals the round in which it is removed.

Why (induction on rounds): a vertex is removed in round \(r + 1\) exactly when, after rounds \(1..r\), at most one neighbour is left. By Claim 1, all layer-\(\le r\) vertices are popped before any layer-\((r+1)\) vertex, and each pop lowers its neighbours' degrees. So the vertex's degree reaches \(1\) exactly while layer-\(r\) vertices are being popped, and it gets layer \(r + 1\).

The same two claims give the classic result for single-source BFS on any unweighted graph: the first time a vertex is reached, its layer is its shortest distance from the start.

2.3 Getting a path, not just the distance

For shortest-path BFS, store, for every vertex, where we came from (its parent). At the end, start at the target, follow parent links back to the start, and reverse. Each step back is one edge of a shortest path, because every parent had distance exactly one less. The lesson notes below show this.

2.4 BFS only works when every step costs the same

If edges have different lengths (roads with kilometres), fewer steps does not mean shorter distance. Then you need Dijkstra's algorithm instead (see Shortest Paths). BFS is the special case where every edge has length \(1\).

Cost: each vertex enters the queue once, so \(O(n + m)\) on a graph and \(O(nm)\) on an \(n \times m\) grid.

3. Templates

3.1 From our slides

The grid BFS template from USACO Algorithm — From Bronze to Silver (16 Jan):

# Need a queue for BFS
queue = []
queue.append((start_x, start_y, 0)) # (x, y, steps)

visited = set()
visited.add((start_x, start_y))

while len(queue) > 0:
    x, y, dist = queue.pop(0) # Pop from front

    if x == target_x and y == target_y:
        print(dist)
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # Check Bounds & Visited
        if (0 <= nx < N and 0 <= ny < M and
            (nx, ny) not in visited):

            visited.add((nx, ny))
            queue.append((nx, ny, dist + 1))

Two things to add in real problems

  1. queue.pop(0) is \(O(\text{queue length})\) per call. On large inputs use collections.deque with popleft(), as in the lesson notes below.
  2. The slide version has no wall check. Add grid[nx][ny] != '#' when the map has obstacles.

3.2 Lesson notes — April 12

Recap

Today we learned BFS and DFS with backtracking.

We first discussed BFS and why it can find shortest paths in an unweighted graph. Since BFS expands layer by layer, the first time we reach a node, we have already found a shortest path to it. If we also need to output a path, we can store the parent of each node and trace backward from the end.

We then applied BFS to grids. A grid problem can be viewed as a graph problem. If the movement changes from four directions to knight moves, we only need to change the direction list. We also discussed queen movement, and the key point is that the number of moves is still finite because the grid is finite.

In the second half, we studied the 4-queens and 8-queens problems. We solved them using DFS with backtracking: place queens column by column, check validity, recurse, and undo after returning.

Notes

BFS

  • BFS expands states layer by layer.
  • In an unweighted graph, BFS gives shortest distances from the start.
  • Standard BFS with distance:
dist = [-1] * n
dist[start] = 0
q = deque([start])

while q:
    u = q.popleft()
    for v in graph[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)
  • To restore one shortest path, save parent:
parent = [-1] * n
parent[start] = start

while q:
    u = q.popleft()
    for v in graph[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            parent[v] = u
            q.append(v)
  • Restore path from end back to start:
path = []
cur = end
while cur != start:
    path.append(cur)
    cur = parent[cur]
path.append(start)
path.reverse()

Grid BFS

  • Treat each cell as a node.
  • dirs stores all allowed moves.
  • To change the movement rule, usually only change dirs.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
  • Example of trying all neighbors:
for dx, dy in dirs:
    nx = x + dx
    ny = y + dy
    if 0 <= nx < n and 0 <= ny < m:
        if grid[nx][ny] != '#':
            ...
  • Knight moves:
dirs = [
    (-1, -2), (1, -2), (-1, 2), (1, 2),
    (-2, -1), (-2, 1), (2, -1), (2, 1)
]
  • Queen moves are still finite on a finite grid.

4. Worked solution — Gardener and Tree

The deque BFS from the lesson notes, started from every leaf at once. read_ints skips the empty line before each test case.

import sys
from collections import deque

input = sys.stdin.readline


def read_ints():
    line = input().split()
    while not line:
        line = input().split()
    return map(int, line)


def solve():
    n, k = read_ints()

    adj = [[] for _ in range(n + 1)]
    deg = [0] * (n + 1)
    for _ in range(n - 1):
        u, v = read_ints()
        adj[u].append(v)
        adj[v].append(u)
        deg[u] += 1
        deg[v] += 1

    layer = [0] * (n + 1)
    q = deque()
    for v in range(1, n + 1):
        if deg[v] <= 1:
            layer[v] = 1
            q.append(v)

    while q:
        u = q.popleft()
        for v in adj[u]:
            deg[v] -= 1
            if deg[v] == 1 and layer[v] == 0:
                layer[v] = layer[u] + 1
                q.append(v)

    remain = 0
    for v in range(1, n + 1):
        if layer[v] > k:
            remain += 1
    print(remain)


t = int(input())
for _ in range(t):
    solve()

The special cases from the statement

A single vertex has degree \(0\), so deg[v] <= 1 makes it a leaf of round 1. With two vertices both have degree \(1\), so both are removed in round 1. Neither needs extra code.

5. Variations you will meet

variation change
8 directions, knight moves only change dirs (see the lesson notes)
multi-source BFS: distance to the nearest of many starts push all starts before the loop (this page)
shortest path + the path itself store parent, walk back (lesson notes)
BFS twice on a tree farthest vertex, then farthest from that: Tree Diameter

6. Common mistakes

Empty lines in the input

int(input()) on an empty line crashes. When the statement says test cases are separated by empty lines, skip them as read_ints does.

Marking visited when popping

Then the same vertex can be pushed many times, which is slow, and its layer may be overwritten. Mark when pushing.

Using a stack instead of a queue

pop() takes the newest element, and that is DFS. Layers are then wrong. BFS needs popleft().

Walking back from the start instead of the end

parent points backwards. Start at the target, walk to the start, then reverse.

Simulating the rounds

Removing leaves round by round is \(O(nk)\). Compute each vertex's layer once instead.

7. Practice

Problem Set Rating Idea
1593E · Gardener and Tree 5-Graph · H 1600 multi-source BFS from leaves (this page)
OJ P2251 April 12 homework — grid BFS
1881F · Minimum Maximum Distance 5-Graph · G 1700 BFS twice, tree diameter idea
1873H · Mad City 5-Graph · I 1700 BFS distances from two people
1702E · Split Into Two Sets 5-Graph · D 1600 BFS colouring
Credits & licenses