Breadth-First Search in Python
Breadth-first search explores every immediate neighbor before moving to the next level and finds shortest paths in unweighted graphs.
What is Breadth-First Search?
Breadth-first search explores every immediate neighbor before moving to the next level and finds shortest paths in unweighted graphs.
Traverse a graph level by level with breadth-first search.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Breadth-First Search in Python visualizer
O(V + E)Use Play or Step to follow each comparison and data movement.
Example code
main.py
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)Expected output
['A', 'B', 'C', 'D', 'E']How it works
The queue stores nodes waiting to be explored, and the visited set prevents cycles. Complexity is O(V + E).
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.