CodeUtility
Making your developer's life easier!
Python Algorithms

Breadth-First Search (BFS) in Python

Explore a graph level by level with a queue, and find the shortest path in an unweighted graph.

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • Representing a graph as a dict of lists
  • Using a deque as the queue
  • Tracking visited nodes
Run in the Python compiler →
BFS from A
  • Alevel 0
    • Blevel 1
      • Dlevel 2
    • Clevel 1
      • Elevel 2
Visit order: A, B, C, D, E.

Nearest nodes first

Breadth-first search explores every immediate neighbor before moving to the next level and finds shortest paths in unweighted graphs.

Key points

  1. Start with the source in the queue and in visited.
  2. Take a node from the front, then add its unvisited neighbours to the back.
  3. Nodes come out in order of distance from the start.
  4. Each node and edge is processed once: O(V + E).

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

Run 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)
Get a Run button for this example

Result of running the code

['A', 'B', 'C', 'D', 'E']

Code explanation

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.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges