9.10 Breadth-First Search (BFS)
You need to explore a graph in order of increasing distance from a starting vertex.
9.10 Breadth-First Search (BFS)
Problem
You need to explore a graph in order of increasing distance from a starting vertex.
Many graph problems are fundamentally questions about proximity:
- What vertices can be reached in one step?
- What vertices can be reached in two steps?
- What is the shortest path in an unweighted graph?
- How many hops separate two users in a social network?
- Which routers are closest to a destination?
- Which states can be reached after exactly k moves?
Depth-First Search explores deeply before backtracking. That behavior is useful for structural analysis, but it does not naturally discover shortest paths.
You need a traversal strategy that expands outward layer by layer.
Solution
Use Breadth-First Search (BFS).
BFS explores vertices in order of increasing distance from the starting vertex.
Consider:
A
/ \\n B C
/ \ \\n D E F
Starting from A, BFS visits:
A
B C
D E F
or:
A
B
C
D
E
F
depending on output formatting.
The key property is that all vertices at distance one are visited before any vertex at distance two.
A standard implementation uses a queue.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
vertex = queue.popleft()
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
The queue drives the breadth-first behavior.
Discussion
The defining idea behind BFS is the frontier.
At any moment, the queue contains vertices that have been discovered but not yet explored.
These vertices form the boundary between explored and unexplored portions of the graph.
Consider:
A
|
B
|
C
|
D
Initially:
queue = [A]
After processing A:
queue = [B]
After processing B:
queue = [C]
The queue always holds the next layer of exploration.
This property leads directly to shortest-path guarantees in unweighted graphs.
Why a Queue Works
DFS uses a stack.
BFS uses a queue.
This small change completely alters traversal behavior.
A queue follows first-in, first-out ordering.
enqueue A
enqueue B
enqueue C
dequeue A
dequeue B
dequeue C
Earlier discoveries are processed first.
As a result, BFS expands uniformly outward from the source.
You can think of BFS as a wave moving through the graph.
Vertices nearest the source are reached first.
Vertices farther away are reached later.
Layered Exploration
Suppose the graph is:
A
/ \\n B C
/ \ \\n D E F
Distances from A are:
| Vertex | Distance |
|---|---|
| A | 0 |
| B | 1 |
| C | 1 |
| D | 2 |
| E | 2 |
| F | 2 |
BFS naturally discovers vertices in this order.
Layer 0:
A
Layer 1:
B C
Layer 2:
D E F
This layering property is the foundation of shortest-path computation.
Recipe: Compute Distances
One of the most useful BFS applications is distance computation.
from collections import deque
def bfs_distance(graph, start):
distance = {
start: 0
}
queue = deque([start])
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in distance:
distance[neighbor] = (
distance[vertex] + 1
)
queue.append(neighbor)
return distance
Example:
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["E"],
"D": [],
"E": [],
}
Output:
{
"A": 0,
"B": 1,
"C": 1,
"D": 2,
"E": 2,
}
These are shortest-path distances measured in edges.
Why BFS Finds Shortest Paths
This is the most important BFS property.
When a vertex is first removed from the queue, BFS has already found the shortest path to it.
The reason is simple.
Vertices enter the queue in increasing distance order.
Every path of length:
0
is processed before paths of length:
1
Every path of length:
1
is processed before paths of length:
2
and so on.
Therefore, the first discovery must be optimal.
This guarantee holds only when every edge has equal cost.
Once weights appear, BFS generally becomes incorrect.
Weighted shortest paths require different algorithms.
Recipe: Recover the Shortest Path
Distances are useful, but sometimes the actual path is needed.
Store parent information during traversal.
from collections import deque
def shortest_path(graph, start, target):
parent = {
start: None
}
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex == target:
break
for neighbor in graph[vertex]:
if neighbor not in parent:
parent[neighbor] = vertex
queue.append(neighbor)
if target not in parent:
return None
path = []
current = target
while current is not None:
path.append(current)
current = parent[current]
path.reverse()
return path
Example:
shortest_path(
graph,
"A",
"E"
)
Output:
["A", "C", "E"]
The path is reconstructed by walking backward through parent pointers.
BFS Trees
Like DFS, BFS builds a traversal tree.
Consider:
A
|\\nB C
| \\nD E
Starting at A, BFS discovers:
A
├── B
├── C
│
├── D
└── E
Each vertex records the edge that first discovered it.
These discovery edges form the BFS tree.
The BFS tree has an important property:
Every root-to-vertex path in the tree is a shortest path.
DFS trees do not provide this guarantee.
Multi-Source BFS
Sometimes multiple starting points exist.
Suppose several servers can provide data.
You want the nearest server for every client.
Instead of running BFS repeatedly, start from all sources simultaneously.
from collections import deque
def multi_source_bfs(graph, sources):
distance = {}
queue = deque()
for source in sources:
distance[source] = 0
queue.append(source)
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in distance:
distance[neighbor] = (
distance[vertex] + 1
)
queue.append(neighbor)
return distance
The algorithm computes the distance to the nearest source.
This pattern appears frequently in routing, facility location, and grid problems.
BFS on Grids
Many interview and competitive-programming problems involve grids rather than explicit graphs.
Example:
S . .
. # .
. . T
Treat each cell as a vertex.
Legal moves become edges.
from collections import deque
def neighbors(grid, row, col):
rows = len(grid)
cols = len(grid[0])
for dr, dc in [
(-1, 0),
(1, 0),
(0, -1),
(0, 1),
]:
nr = row + dr
nc = col + dc
if (
0 <= nr < rows
and 0 <= nc < cols
and grid[nr][nc] != "#"
):
yield nr, nc
BFS then finds the shortest route through the grid.
This modeling technique appears repeatedly throughout algorithmic problem solving.
BFS and Bipartite Graphs
BFS naturally assigns levels.
Vertices at even distance belong to one layer.
Vertices at odd distance belong to another.
This observation leads to a simple bipartite-graph test.
from collections import deque
def is_bipartite(graph):
color = {}
for start in graph:
if start in color:
continue
color[start] = 0
queue = deque([start])
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in color:
color[neighbor] = (
1 - color[vertex]
)
queue.append(neighbor)
elif color[neighbor] == color[vertex]:
return False
return True
BFS layers provide the coloring automatically.
BFS vs DFS
The two algorithms often solve similar reachability problems.
Their behavior differs significantly.
| Property | DFS | BFS |
|---|---|---|
| Primary structure | Stack | Queue |
| Exploration style | Deep first | Layer first |
| Shortest paths | No | Yes (unweighted) |
| Memory usage | Often smaller | Often larger |
| Topological sort | Yes | No |
| Connected components | Yes | Yes |
| Cycle detection | Excellent | Possible |
| Distance computation | Indirect | Natural |
Neither algorithm dominates the other.
Each has situations where it is the natural choice.
Complexity Analysis
Let:
V= number of verticesE= number of edges
Each vertex enters the queue once.
Each edge is examined at most once in directed graphs and at most twice in undirected graphs.
Therefore:
| Operation | Complexity |
|---|---|
| BFS traversal | O(V + E) |
| Distance computation | O(V + E) |
| Shortest-path recovery | O(V + E) |
| Queue storage | O(V) |
| Parent storage | O(V) |
The complexity matches DFS.
The difference lies entirely in traversal order.
Common Pitfalls
Do not mark vertices visited after removing them from the queue.
Mark them when they are added.
Otherwise duplicate work may occur.
Incorrect:
queue.append(neighbor)
Correct:
visited.add(neighbor)
queue.append(neighbor)
Do not use BFS for weighted shortest paths.
Do not assume queue order is arbitrary.
The shortest-path guarantee depends on strict FIFO behavior.
Do not forget disconnected components.
A single BFS explores only the reachable region.
Do not confuse BFS levels with DFS depth.
They represent different concepts.
Recipe: Reachability Test
Sometimes only a yes-or-no answer is required.
from collections import deque
def reachable(graph, source, target):
visited = {source}
queue = deque([source])
while queue:
vertex = queue.popleft()
if vertex == target:
return True
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return False
This is one of the most frequently used BFS patterns.
Takeaway
Breadth-First Search explores a graph layer by layer using a queue. Its defining property is that vertices are discovered in order of increasing distance from the source. This makes BFS the standard algorithm for shortest paths in unweighted graphs, distance computation, level construction, bipartite testing, and many grid-based search problems. Understanding queues, frontiers, BFS trees, parent reconstruction, and distance layers provides the foundation for a large family of graph algorithms that depend on shortest-path structure.