Python graphs and breadth-first search
Visit reachable vertices level by level without revisiting cycles.
On this page
Queues, dictionaries, and sets.
- Visit reachable vertices level by level without revisiting cycles.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
An adjacency list maps a vertex to its neighbors. BFS uses a queue to explore discovered vertices in distance order from the start in an unweighted graph.
Mark a vertex seen when enqueuing it, not later when removing it. This prevents multiple neighbors from scheduling the same vertex repeatedly.
Code example
from collections import deque
def bfs(graph, start):
seen = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
return order
graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["D"], "D": []}
print(bfs(graph, "A"))
assert bfs({}, "Z") == ["Z"]['A', 'B', 'C', 'D']
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
from collections import deque def bfs(graph, start): seen = {start} queue = deque([start]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph.get(node, []): if neighbor not in seen: seen.add(neighbor) queue.append(neighbor) return order graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["D"], "D": []}print(bfs(graph, "A"))assert bfs({}, "Z") == ["Z"]Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Begin at A. | queue = [A], seen = {A} | — | |
| Remove A and append it to order. | order = [A] | — | |
| Discover B then C from A. | queue = [B, C], seen = {A, B, C} | — | |
| Remove B; A is already seen, but D is new. | order = [A, B] | — | |
| Enqueue D once. | queue = [C, D], seen = {A, B, C, D} | — | |
| Remove C, skip already-seen D, then remove D. | order = [A, B, C, D], queue = [] | — | |
| Print the traversal order. | order = [A, B, C, D], queue = [] | ['A', 'B', 'C', 'D'] |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
Expected O(V+E) time and O(V) auxiliary space over the reachable graph, with average constant-time set operations.
- Neighbor ordering controls ties in traversal order.
- Only vertices reachable from start are visited. A missing key is treated as a vertex with no outgoing edges.
Try it yourself
Add a disconnected vertex E. Will BFS from A visit it?
Reveal answer and reasoning
No. Run a separate search from E or iterate over all unvisited vertices to cover every component.