Breadth-First Search (BFS)

#How does it work?

Breadth-first search (BFS) visits a graph's nodes layer by layer, in order of their distance from the start: first all neighbours, then the neighbours' neighbours, and so on.

A queue gives this order: discovered nodes join the back, and the next node is taken from the front. A visited set makes sure no node is added twice.

In an unweighted graph, the path on which BFS first discovers a node is a shortest path to it. Record where each node was discovered from (prev) and you can trace the path back from the target.

#Try it yourself

#Step by step

1. 01Put the start node in the queue and mark it visited.
2. 02Until the queue is empty, take a node (u) from the front.
3. 03For each neighbour v of u not seen yet: mark it, set prev[v] = u and add it to the back of the queue.
4. 04For a shortest path: stop when the target leaves the queue and follow prev[] from the target back to the start.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from collections import deque

# Undirected graph as adjacency lists (neighbours in increasing order).
EDGES = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]
graph = {v: [] for v in range(1, 8)}
for a, b in EDGES:
    graph[a].append(b)
    graph[b].append(a)
for v in graph:
    graph[v].sort()


def bfs(start: int) -> list:
    order, visited, queue = [], {start}, deque([start])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visited.add(v)  # mark when queued, so nothing is queued twice
                queue.append(v)
    return order


def shortest_path(start: int, target: int) -> list:
    prev, queue = {start: None}, deque([start])
    while queue:
        u = queue.popleft()
        if u == target:
            break
        for v in graph[u]:
            if v not in prev:
                prev[v] = u
                queue.append(v)
    if target not in prev:
        return []
    path = [target]
    while prev[path[-1]] is not None:
        path.append(prev[path[-1]])
    return path[::-1]


print(" ".join(map(str, bfs(1))))               # layer by layer
print(" ".join(map(str, shortest_path(1, 7))))  # fewest edges from 1 to 7

#Complexity

V is the number of nodes and E the number of edges. Each node enters the queue at most once and each edge is looked at once from each end. With different edge weights BFS can't find shortest paths; that takes Dijkstra.

#When to use it?

Shortest paths in unweighted graphs (mazes, game maps, "how many steps" questions), friend-of-a-friend suggestions in social networks, web crawlers exploring layer by layer, broadcasting in a network and checking whether a graph is bipartite all use BFS.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Dijkstra's Algorithm
• Topological Sort