Breadth-First Search (BFS)
Learn how BFS explores a graph level by level using a queue, and why it finds the shortest path in unweighted graphs.
Breadth-First Search (BFS)
BFS explores a graph level by level — visiting every neighbor of the starting vertex before moving on to their neighbors. It uses a queue to track which vertex to visit next, always processing the oldest discovered vertex first.
This level-by-level exploration is exactly why BFS guarantees the shortest path in an unweighted graph — it finds all vertices at distance 1, then all at distance 2, and so on. The first time it reaches the target, that is guaranteed to be via the shortest route.
How it works
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
vertex = queue.popleft() # take the oldest discovered vertex
order.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) # discovered, will visit later
return order
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
print(bfs(graph, "A")) # ['A', 'B', 'C', 'D', 'E', 'F']Why a queue, not a stack
The queue is what enforces level-by-level order. New neighbors are added to the back of the queue, but the next vertex to process is taken from the front — meaning everything discovered earlier (closer to the start) gets processed before anything discovered later (farther from the start).
Step 1: queue = [A] visit A, discover B, C
Step 2: queue = [B, C] visit B, discover D, E
Step 3: queue = [C, D, E] visit C, discover F
Step 4: queue = [D, E, F] visit D, nothing new
Step 5: queue = [E, F] visit E, nothing new
Step 6: queue = [F] visit F, nothing newNotice B and C (distance 1 from A) are both processed before D, E, F (distance 2) — even though F was discovered while processing C, it waits behind D and E in the queue.
If you swap the queue for a stack, you get DFS instead — depth-first, not breadth-first. The data structure alone determines the entire exploration strategy. This is the single most important distinction between BFS and DFS.
Finding shortest path with BFS
Track each vertex's distance and predecessor while traversing, then walk backward from the target to reconstruct the path.
from collections import deque
def bfs_shortest_path(graph, start, target):
visited = {start}
queue = deque([start])
predecessor = {start: None}
while queue:
vertex = queue.popleft()
if vertex == target:
# reconstruct path by walking backward through predecessors
path = []
while vertex is not None:
path.append(vertex)
vertex = predecessor[vertex]
return path[::-1] # reverse to get start → target order
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
predecessor[neighbor] = vertex
queue.append(neighbor)
return None # target unreachable
print(bfs_shortest_path(graph, "A", "F")) # ['A', 'C', 'F']Real use cases
Shortest path in unweighted graphs — social network "degrees of separation," GPS routing on equal-cost roads.
Web crawling — discover all pages reachable within N clicks.
Finding all connected components — run BFS from every unvisited vertex.
Puzzle solving — finding the minimum number of moves to solve a puzzle (like a sliding tile puzzle), where each state is a vertex.
Peer-to-peer networks — finding the nearest peer or broadcasting to all nodes within a certain hop count.
BFS on a tree vs BFS on a graph
Tree-level traversal (covered in the trees section) is BFS on a tree — the same algorithm, simplified because trees have no cycles. On a general graph, the visited set becomes essential — without it, BFS could loop forever revisiting the same vertices through a cycle.
# tree level-order — no visited set needed, trees have no cycles
def level_order(root):
queue = deque([root])
while queue:
node = queue.popleft()
...
# graph BFS — visited set is required to avoid infinite loops
def bfs(graph, start):
visited = {start} # critical for graphs with cycles
queue = deque([start])
...Complexity
| Time | Space | |
|---|---|---|
| BFS | O(V + E) | O(V) |
Where V is the number of vertices and E is the number of edges. Every vertex is visited once, and every edge is examined once when checking neighbors.