Breadth-first search explores a graph level by level using a queue. It finds the shortest path in unweighted graphs in O(V + E) and is the foundation of many graph algorithms (web crawling, social-network distance, network broadcast).
BFS answers the question "what can I reach, and in how few steps?" Starting from a source vertex it visits every vertex at distance 1, then every vertex at distance 2, and so on. The diagram shows the example graph used in the code below: A is level 0, B and C are level 1, D and E are level 2, and F is level 3. Because every vertex is first reached through a shortest route, recording each vertex's parent when it is discovered gives a shortest-path tree for the whole graph, not only for one target.
The key data structure is a FIFO queue. Vertices enter the queue in order of distance, so the queue never contains vertices more than one level apart. This is what separates BFS from depth-first search, which uses a stack (or recursion) and dives along one branch before backtracking.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(V+E) |
Θ(V+E) |
O(V+E) |
O(V) |
Start with the source in a queue and a visited set. Repeatedly: pop the front node, visit its unvisited neighbors, mark them visited, and enqueue them. The queue ensures nodes are processed in order of distance from the source.
from collections import deque
def bfs(graph, start):
"""BFS from start; yields nodes in BFS order."""
visited = {start}
q = deque([start])
while q:
node = q.popleft()
yield node
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
q.append(nbr)
def shortest_path(graph, start, goal):
"""Shortest unweighted path from start to goal."""
if start == goal: return [start]
parents = {start: None}
q = deque([start])
while q:
node = q.popleft()
for nbr in graph[node]:
if nbr in parents: continue
parents[nbr] = node
if nbr == goal:
path = [goal]
while parents[path[-1]] is not None:
path.append(parents[path[-1]])
return path[::-1]
q.append(nbr)
return None
graph = {
"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": [],
}
print(list(bfs(graph, "A"))) # ['A', 'B', 'C', 'D', 'E', 'F']
print(shortest_path(graph, "A", "F")) # ['A', 'B', 'D', 'F']The trace runs bfs(graph, "A"). At each step the front vertex is popped and its unvisited neighbours are appended. Notice that D is discovered from B, so when C is processed, D is already in the visited set and is not enqueued twice. Marking a vertex visited when it is enqueued, not when it is popped, is what guarantees each vertex enters the queue at most once and keeps the algorithm at O(V + E). The output order is A, B, C, D, E, F.
A very common use of BFS is finding the minimum number of moves in a grid maze, where each open cell is a vertex and edges connect orthogonal neighbours. The graph is implicit: neighbours are computed on the fly instead of stored in an adjacency list.
from collections import deque
def grid_shortest(grid, start, goal):
"""grid: list of strings, '#' is a wall. Returns number of moves or -1."""
rows, cols = 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 < rows and 0 <= nc < cols \
and grid[nr][nc] != '#' and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
q.append((nr, nc))
return -1
maze = ["..#.",
".##.",
"....",
"#.#."]
print(grid_shortest(maze, (0, 0), (0, 3))) # 7
The dist dictionary doubles as the visited set. The same pattern solves word ladders (vertices are words, edges differ by one letter), minimum knight moves, and social "degrees of separation" queries. For multiple sources (for example, distance from the nearest exit), seed the queue with all sources at distance 0: this is multi-source BFS.
len(q) at the start of each round and pop exactly that many to handle one level at a time (used for binary-tree level-order traversal).list with pop(0) as the queue makes each pop O(n) and the whole search O(V^2); always use collections.deque.| Property | BFS | DFS |
|---|---|---|
| Frontier structure | Queue (FIFO) | Stack or recursion (LIFO) |
| Shortest path (unweighted) | Yes | No |
| Memory | O(width of graph) | O(depth of graph) |
| Typical uses | Distances, levels, nearest target | Topological sort, cycle detection, backtracking |
Choose BFS when the answer depends on distance from the start; choose DFS when you need to explore whole branches or the graph is very wide.