Breadth First Search in Python (BFS with Examples)

Breadth first search in Python explores a graph level by level: first the start node, then all its neighbors, then their neighbors, and so on. You build it with a queue from collections.deque and a set of visited nodes:

queue = deque([start]); visited = {start}
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in visited:
            visited.add(nxt); queue.append(nxt)

Every BFS here uses only the standard library, and I ran each one with Python 3.12.5 in Command Prompt.

We’ll write a basic BFS on a map of US flight routes, count hops, find the shortest path, solve a grid maze, traverse a binary tree by level, and see why deque matters.

How breadth first search works

BFS uses a first-in, first-out queue. Nodes are visited in the order they were discovered, so everything one step away gets visited before anything two steps away.

1. Put the start node in the queue and mark it visited.
2. Take the node at the front of the queue.
3. Add each unvisited neighbor to the back of the queue and mark it visited.
4. Repeat until the queue is empty (or you find your goal).

BFS in Python with a deque

Here the graph is a dictionary: each city maps to a list of cities with a direct flight. This adjacency-list format is the most common way to store a graph in Python:

from collections import deque

routes = {
    "Seattle": ["Denver", "Chicago"],
    "Denver": ["Seattle", "Dallas", "Chicago"],
    "Chicago": ["Seattle", "Denver", "New York", "Atlanta"],
    "Dallas": ["Denver", "Atlanta", "Miami"],
    "Atlanta": ["Chicago", "Dallas", "Miami", "New York"],
    "New York": ["Chicago", "Atlanta", "Boston"],
    "Miami": ["Dallas", "Atlanta"],
    "Boston": ["New York"],
}

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        city = queue.popleft()          # take from the front
        order.append(city)
        for nxt in graph[city]:
            if nxt not in visited:
                visited.add(nxt)        # mark when queued, not when popped
                queue.append(nxt)       # add to the back
    return order

print(bfs(routes, "Seattle"))

Output:

['Seattle', 'Denver', 'Chicago', 'Dallas', 'New York', 'Atlanta', 'Miami', 'Boston']

I always mark a node visited when it’s added to the queue, not when it’s popped. Otherwise the same city can be queued several times from different neighbors.

Counting levels: how many hops away is each node?

Because BFS moves outward one ring at a time, you can record each node’s distance as you discover it. That’s the number of edges on the shortest route:

from collections import deque

routes = {
    "Seattle": ["Denver", "Chicago"],
    "Denver": ["Seattle", "Dallas", "Chicago"],
    "Chicago": ["Seattle", "Denver", "New York", "Atlanta"],
    "Dallas": ["Denver", "Atlanta", "Miami"],
    "Atlanta": ["Chicago", "Dallas", "Miami", "New York"],
    "New York": ["Chicago", "Atlanta", "Boston"],
    "Miami": ["Dallas", "Atlanta"],
    "Boston": ["New York"],
}

def hops_from(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        city = queue.popleft()
        for nxt in graph[city]:
            if nxt not in dist:
                dist[nxt] = dist[city] + 1
                queue.append(nxt)
    return dist

for city, hops in hops_from(routes, "Seattle").items():
    print(f"{city:<9} {hops} flight(s) away")

Output:

Seattle   0 flight(s) away
Denver    1 flight(s) away
Chicago   1 flight(s) away
Dallas    2 flight(s) away
New York  2 flight(s) away
Atlanta   2 flight(s) away
Miami     3 flight(s) away
Boston    3 flight(s) away

Store the distances in a dictionary and it doubles as your visited set. For more on that structure, see dictionaries of lists.

How do you find the shortest path with BFS?

Keep a parent dictionary that records where you came from. When you reach the goal, follow the parents back to the start and reverse the list:

from collections import deque

routes = {
    "Seattle": ["Denver", "Chicago"],
    "Denver": ["Seattle", "Dallas", "Chicago"],
    "Chicago": ["Seattle", "Denver", "New York", "Atlanta"],
    "Dallas": ["Denver", "Atlanta", "Miami"],
    "Atlanta": ["Chicago", "Dallas", "Miami", "New York"],
    "New York": ["Chicago", "Atlanta", "Boston"],
    "Miami": ["Dallas", "Atlanta"],
    "Boston": ["New York"],
}

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        city = queue.popleft()
        if city == goal:
            path = []
            while city is not None:      # walk back through the parents
                path.append(city)
                city = parent[city]
            return path[::-1]
        for nxt in graph[city]:
            if nxt not in parent:
                parent[nxt] = city
                queue.append(nxt)
    return None

print(" -> ".join(shortest_path(routes, "Seattle", "Miami")))
print(" -> ".join(shortest_path(routes, "Boston", "Dallas")))
print(shortest_path({"A": ["B"], "B": [], "C": []}, "A", "C"))

Output:

Seattle -> Denver -> Dallas -> Miami
Boston -> New York -> Atlanta -> Dallas
None

This only finds the fewest edges. If each flight has a different cost or distance, you need Dijkstra’s algorithm, which swaps the queue for a priority queue.

Solving a maze with breadth first search

A grid is just a graph where each open cell connects to its four neighbors. BFS from the start finds the shortest way to the exit:

from collections import deque

maze = [
    "S.#.....",
    ".##.###.",
    "....#...",
    "##.##.#.",
    "...#..#E",
]

def solve(maze):
    rows, cols = len(maze), len(maze[0])
    start = next((r, c) for r in range(rows) for c in range(cols) if maze[r][c] == "S")
    parent = {start: None}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if maze[r][c] == "E":
            path, cell = [], (r, c)
            while cell:
                path.append(cell)
                cell = parent[cell]
            return path[::-1]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] != "#" and (nr, nc) not in parent:
                parent[(nr, nc)] = (r, c)
                queue.append((nr, nc))

path = solve(maze)
print("steps:", len(path) - 1)
grid = [list(row) for row in maze]
for r, c in path[1:-1]:
    grid[r][c] = "*"
print("\n".join("".join(row) for row in grid))

Output:

steps: 15
S.#*****
*##*###*
****#..*
##.##.#*
...#..#E

Storing the maze as a list of lists lets you mark the path in place, which is what the last few lines do.

Level order traversal of a binary tree

On a tree, BFS is called level order traversal. Process the queue one level at a time by looping over its current length:

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

#        50
#      /    \
#    30      70
#   /  \       \
#  20  40       80
root = Node(50, Node(30, Node(20), Node(40)), Node(70, None, Node(80)))

def level_order(root):
    levels, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):       # everything in the queue now is one level
            node = queue.popleft()
            level.append(node.val)
            for child in (node.left, node.right):
                if child:
                    queue.append(child)
        levels.append(level)
    return levels

print(level_order(root))

Output:

[[50], [30, 70], [20, 40, 80]]

Trees have no cycles, so you don’t need a visited set here. My Python binary tree guide covers building and searching trees.

Why use deque instead of a list for BFS?

list.pop(0) shifts every remaining item, so it gets slower as the list grows. deque.popleft() takes the same tiny time no matter how long the queue is:

import timeit
from collections import deque

n = 50_000
list_time = timeit.timeit("q = list(range(n))\nwhile q: q.pop(0)", globals={"n": n}, number=1)
deque_time = timeit.timeit("q = deque(range(n))\nwhile q: q.popleft()", globals={"n": n, "deque": deque}, number=1)

print(f"list.pop(0):     {list_time:.3f} s")
print(f"deque.popleft(): {deque_time:.4f} s")

Output:

list.pop(0):     2.398 s
deque.popleft(): 0.0015 s

On big graphs that difference turns a fast BFS into a slow one, so deque is the right tool every time.

BFS vs DFS

	Breadth first search	Depth first search
Data structure	Queue (deque)	Stack or recursion
Visits	Level by level	One branch to the end, then backtracks
Shortest path (unweighted)	Yes	No
Memory	Can be large on wide graphs	Proportional to depth
Time	O(V + E)	O(V + E)

Use BFS when you need the shortest path or the nearest match. Use DFS for things like detecting cycles, topological sorting, or exploring every possible path.

More algorithm guides you might like:

• Binary search in Python
• Sorting algorithms in Python
• Priority queue in Python
• Python while loop

Frequently asked questions