BFS and Shortest Path by Number of Edges
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)How many connections separate two people? How many moves from one position to another? When every edge counts the same, breadth-first search answers by visiting the graph in rings.
Visit level by level
Breadth-first search (BFS) visits a graph level by level from a start node: all nodes one edge away, then two edges away, and so on. It uses a queue.
Drop a stone in a pond and the ripples reach near points first. Breadth-first search spreads the same way: first the start, then everything one edge away, then two edges away.
The queue and the visited set
A queue gives out nodes in the order they arrived, so nearer nodes are handled before farther ones. A set of seen nodes stops the search from going round a cycle forever.
from collections import deque
def bfs_order(graph, start): seen = {start} queue = deque([start]) order = [] while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: if nxt not in seen: seen.add(nxt) queue.append(nxt) return orderExample 1 · BFS visiting order
from collections import defaultdict, deque
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def bfs_order(graph, start): seen = {start} queue = deque([start]) order = [] while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: if nxt not in seen: seen.add(nxt) queue.append(nxt) return order
print(bfs_order(graph, 0))print(bfs_order(graph, 4))[0, 1, 2, 3, 4] [4, 3, 1, 2, 0]
What this code does
- From node 0 the search takes 1 and 2 first, then 3 through node 1, then 4.
- Starting from 4 the order changes, because the levels are measured from the start.
Example 2 · Mark when adding, not when removing
from collections import defaultdict, deque
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def pushes(mark_on_add): seen = {0} queue = deque([0]) count = 1 while queue: node = queue.popleft() if not mark_on_add: if node in seen and node != 0: continue seen.add(node) for nxt in graph[node]: if nxt not in seen: if mark_on_add: seen.add(nxt) queue.append(nxt) count += 1 return count
print(pushes(True), pushes(False))5 6
What this code does
- Marking late lets node 3 enter the queue twice, once from node 1 and once from node 2.
- On large graphs this duplicate work grows, so always mark when you add.
Mark a node as seen when you add it to the queue, not when you remove it. Use deque: popleft() is O(1), while list.pop(0) moves every item. Every node and edge is touched once, so the time is O(n + m).
Shortest path by number of edges
In a graph without weights, the shortest path between two nodes is the one with the fewest edges. BFS finds its length from one start node to every other node.
BFS reaches every node by the fewest edges possible, because nearer levels finish first. Store the distance when a node is first reached, and that number is final.
def distances(graph, start): dist = {start: 0} queue = deque([start]) while queue: node = queue.popleft() for nxt in graph[node]: if nxt not in dist: dist[nxt] = dist[node] + 1 queue.append(nxt) return distExample 3 · Brute force: try every path
from collections import defaultdict, deque
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def shortest_slow(node, goal, path): if node == goal: return len(path) - 1 best = None for nxt in graph[node]: if nxt not in path: found = shortest_slow(nxt, goal, path + [nxt]) if found is not None and (best is None or found < best): best = found return best
print(shortest_slow(0, 4, [0]))3
What this code does
- This tries every simple path and keeps the shortest. It is correct but can take exponential time.
- BFS finds the same answer in O(n + m), so use it.
Example 4 · Distances from a start node
from collections import defaultdict, deque
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def distances(graph, start): dist = {start: 0} queue = deque([start]) while queue: node = queue.popleft() for nxt in graph[node]: if nxt not in dist: dist[nxt] = dist[node] + 1 queue.append(nxt) return dist
print(distances(graph, 0)){0: 0, 1: 1, 2: 1, 3: 2, 4: 3}What this code does
- Node 3 is reached first through node 1 with distance 2. Later routes cannot beat it.
- The queue order guarantees that the first distance written is the smallest.
The dictionary is both the distance table and the seen set. A node missing from it cannot be reached.
Rebuilding the path itself
To print the route and not only its length, remember for each node the node it came from. Walk back from the goal through these parents, then reverse the list.
parent = {start: None}# ... same BFS loop, but when a new node is found:parent[nxt] = node
path = []while goal is not None: path.append(goal) goal = parent[goal]path.reverse()Example 5 · The shortest path itself
from collections import defaultdict, deque
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def shortest_path(graph, start, goal): parent = {start: None} queue = deque([start]) while queue: node = queue.popleft() if node == goal: break for nxt in graph[node]: if nxt not in parent: parent[nxt] = node queue.append(nxt) if goal not in parent: return None path = [] while goal is not None: path.append(goal) goal = parent[goal] return path[::-1]
print(shortest_path(graph, 0, 4))print(shortest_path(graph, 4, 1))[0, 1, 3, 4] [4, 3, 1]
What this code does
- Parents lead back from the goal: 4 came from 3, 3 from 1, 1 from 0.
- A different parent order could give [0, 2, 3, 4], which is equally short.
Example 6 · A node that cannot be reached
from collections import defaultdict, deque
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 6)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)
def distances(graph, start): dist = {start: 0} queue = deque([start]) while queue: node = queue.popleft() for nxt in graph[node]: if nxt not in dist: dist[nxt] = dist[node] + 1 queue.append(nxt) return dist
dist = distances(graph, 0)print(dist.get(6, -1))print(dist.get(4, -1))-1 3
What this code does
- Nodes 5 and 6 form a separate piece, so BFS never reaches them.
dist.get(node, -1)turns "not reached" into the usual answer -1.
Following parents from the goal back to the start gives one shortest route. If the goal never gets a parent, there is no route.
Next step
Check your understanding
11 quick questions