DSA course menu
Breadth-First Search (BFS) in Python: Shortest Paths in Unweighted Graphs
Learn breadth-first search with a queue: visiting a graph level by level, finding shortest paths and distances in unweighted graphs, rebuilding the path, BFS on grids and multi-source BFS.
On this page
Breadth-first search (BFS) explores a graph in rings: first the start vertex, then all its neighbours, then all their unvisited neighbours, and so on. Because it reaches every vertex at distance 1 before any at distance 2, BFS finds the shortest path (fewest edges) in an unweighted graph.
BFS uses a queue: vertices are processed in the order they were discovered.
The algorithm#
- Put the start vertex in the queue and mark it as visited.
- While the queue is not empty: take the front vertex, and for each neighbour that is not yet visited, mark it visited and add it to the back of the queue.
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def bfs(graph, start):
visited = {start}
order = []
queue = deque([start])
while queue:
vertex = queue.popleft()
order.append(vertex)
for nxt in graph[vertex]:
if nxt not in visited:
visited.add(nxt) # mark when added, not when removed
queue.append(nxt)
return order
print(bfs(graph, "A"))['A', 'B', 'C', 'D', 'E', 'F']Every vertex enters the queue once and every edge is examined once (twice for undirected graphs): O(V + E) time and O(V) space.
Distances and shortest paths#
Record each vertex's distance and the vertex it was discovered from (its parent). Following parents backwards from the target rebuilds the shortest path:
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def shortest_path(graph, start, goal):
parent = {start: None}
distance = {start: 0}
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex == goal:
break
for nxt in graph[vertex]:
if nxt not in parent:
parent[nxt] = vertex
distance[nxt] = distance[vertex] + 1
queue.append(nxt)
if goal not in parent:
return None
path, node = [], goal
while node is not None:
path.append(node)
node = parent[node]
return path[::-1], distance[goal]
print(shortest_path(graph, "A", "F"))
print(shortest_path(graph, "D", "F"))(['A', 'C', 'F'], 2)
(['D', 'B', 'E', 'F'], 3)Here the parent dictionary doubles as the visited set.
BFS on a grid#
In a maze, each open cell is a vertex and its up/down/left/right neighbours are edges. BFS finds the fewest moves from start to exit:
from collections import deque
maze = [
"S.#.....",
".##.###.",
"....#...",
"#.#...#E",
]
def maze_steps(maze):
rows, cols = len(maze), len(maze[0])
start = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "S")
queue = deque([(start, 0)])
seen = {start}
while queue:
(r, c), steps = queue.popleft()
if maze[r][c] == "E":
return steps
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != "#" and (nr, nc) not in seen:
seen.add((nr, nc))
queue.append(((nr, nc), steps + 1))
return -1
print(maze_steps(maze))12Multi-source BFS#
Start BFS from several vertices at once by putting them all in the queue at distance 0. Each cell then gets its distance to the nearest source. Example: minutes until every orange in a box is rotten, if rotten oranges (2) spoil fresh neighbours (1) each minute:
from collections import deque
def minutes_to_rot(box):
rows, cols = len(box), len(box[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if box[r][c] == 2:
queue.append((r, c, 0))
elif box[r][c] == 1:
fresh += 1
minutes = 0
while queue:
r, c, t = queue.popleft()
minutes = max(minutes, t)
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and box[nr][nc] == 1:
box[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, t + 1))
return minutes if fresh == 0 else -1
print(minutes_to_rot([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
print(minutes_to_rot([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))4
-1In the second box the bottom-left orange is cut off by empty cells, so it never rots and the answer is -1.
Common mistakes#
Practice#
Practice exercise
Word ladder: change one letter at a time to turn start into end, where every intermediate word must be in the word list. Write ladder_length(start, end, words) that returns the number of words in the shortest sequence (including both ends), or 0.
Show hint
Each word is a vertex; two words are connected if they differ in exactly one letter. BFS from start. To find neighbours, try replacing each letter with a–z and keep candidates that are in the word set.
Show solution
from collections import deque
from string import ascii_lowercase
def ladder_length(start, end, words):
words = set(words)
if end not in words:
return 0
queue = deque([(start, 1)])
seen = {start}
while queue:
word, length = queue.popleft()
if word == end:
return length
for i in range(len(word)):
for ch in ascii_lowercase:
candidate = word[:i] + ch + word[i + 1:]
if candidate in words and candidate not in seen:
seen.add(candidate)
queue.append((candidate, length + 1))
return 0
words = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladder_length("hit", "cog", words))
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))5
0The shortest ladder is hit → hot → dot → dog → cog: 5 words.
Key takeaway#
Next: going deep before going wide, with Depth-First Search (DFS).
Finished this lesson?