Python graphs and breadth-first search
Visit reachable vertices level by level without revisiting cycles.
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']
Explanation
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.
Explore the dry run
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'] |
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.