DSA · Chapter 25 of 40
Breadth-First Search
BFS explores a graph level by level using a queue, visiting all neighbours of a vertex before going deeper. In an unweighted graph BFS finds the shortest path in terms of number of edges.
It runs in O(V + E) with an adjacency list and needs a visited set to avoid revisiting vertices in cyclic graphs.
Shortest path
Store the distance when you first enqueue a vertex; because BFS reaches each vertex by the fewest edges, that first distance is optimal.
Grid problems
Treat each cell as a vertex and its four or eight neighbours as edges — flood fill, shortest maze path and rotting oranges are all BFS.
Example 1 (python)
from collections import deque
def bfs(graph, start):
seen = {start}
q = deque([start])
order = []
while q:
v = q.popleft()
order.append(v)
for n in graph[v]:
if n not in seen:
seen.add(n)
q.append(n)
return order
print(bfs(graph, 'A'))Output
['A', 'B', 'C', 'D']Neighbours are marked visited when enqueued, not when dequeued.
Example 2 (python)
def shortest(graph, start, goal):
from collections import deque
q = deque([(start, 0)])
seen = {start}
while q:
v, d = q.popleft()
if v == goal:
return d
for n in graph[v]:
if n not in seen:
seen.add(n)
q.append((n, d + 1))
return -1
print(shortest(graph, 'A', 'D'))Output
2BFS gives the minimum number of edges in an unweighted graph.
Key points
- BFS uses a queue and explores level by level.
- It finds shortest paths in unweighted graphs.
- Complexity is O(V + E).
- Mark vertices visited when enqueuing to avoid duplicates.
💡 Note: Grid shortest-path questions are almost always BFS, not DFS.