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).
| 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']