Breadth-First Search (BFS)
DSA · Graphs
Theory
BFS explores a graph level by level: it visits the start vertex, then all its neighbours, then their neighbours, using a queue and a visited set. Because it expands in rings of increasing distance, the first time BFS reaches a vertex is via the fewest edges, so it finds shortest paths in unweighted graphs. It runs in O(V + E) time.
Why we use it
BFS gives the shortest number of steps between nodes and explores closest options first.
When to use it
Use BFS for shortest paths in unweighted graphs or grids, degrees of separation, spreading processes (rotting oranges), and level-by-level exploration.
How it works
- queue = [start], visited = {start}
- Queue empty? Yes: Done. No: u = pop front, visit u.
- For each neighbour v of u
- v not visited? Yes: Mark visited, push v. No: Skip.
- Visits in order of distance (fewest edges)
Syntax
queue = deque([start]); visited = {start}
while queue:
v = queue.popleft()
for nb in graph[v]:
if nb not in visited:
visited.add(nb); queue.append(nb)
Time: O(V + E) Space: O(V)Example
from collections import deque
graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": ["F"], "F": []}
def bfs_shortest(start, goal):
q = deque([[start]])
visited = {start}
while q:
path = q.popleft()
node = path[-1]
if node == goal:
return path
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
q.append(path + [nb])
return None
print("Shortest path A to F:", " -> ".join(bfs_shortest("A", "F")))Key points
- Uses a queue
- Explores level by level
- Shortest path in unweighted graphs
- O(V + E) time