Breadth-first search in Python: the queue choice changes the run time

Breadth-first search is a queue problem before it is a graph problem. The baseline below uses list.pop(0), which shifts the remaining queue on every removal. The replacement uses collections.deque.popleft(), the operation Python documents for queues. On this Raspberry Pi, both versions return the same traversal and distance arrays, but the deque version is 3.06 times faster on the 16,000-vertex test graph.

The graph has 4 extra random outgoing edges per vertex, plus a chain that keeps every vertex reachable. The generator uses seed 20260930, and each case is timed seven times. The medians are 0.503 ms versus 0.524 ms at 500 vertices, 14.634 ms versus 31.603 ms at 8,000, and 30.627 ms versus 93.694 ms at 16,000. These are measurements of the two implementations below on this machine, not a promise about every graph or Python build.

from __future__ import annotations
import json
import platform
import random
import statistics
import sys
import timeit
from collections import deque
def make_graph(vertex_count: int, degree: int = 4, seed: int = 20260930) -> list[list[int]]:
    """Build one reproducible directed graph with a reachable chain and extra edges."""
    rng = random.Random(seed + vertex_count)
    graph = [[] for _ in range(vertex_count)]
    for vertex in range(vertex_count - 1):
        graph[vertex].append(vertex + 1)
    for vertex in range(vertex_count):
        candidates = {rng.randrange(vertex_count) for _ in range(degree)}
        candidates.discard(vertex)
        graph[vertex].extend(sorted(candidates))
    return graph
def bfs_deque(graph: list[list[int]], start: int) -> tuple[list[int], list[int]]:
    visited = bytearray(len(graph))
    distance = [-1] * len(graph)
    order: list[int] = []
    queue = deque([start])
    visited[start] = 1
    distance[start] = 0
    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        next_distance = distance[vertex] + 1
        for neighbour in graph[vertex]:
            if not visited[neighbour]:
                visited[neighbour] = 1
                distance[neighbour] = next_distance
                queue.append(neighbour)
    return order, distance
def bfs_list_pop_zero(graph: list[list[int]], start: int) -> tuple[list[int], list[int]]:
    visited = bytearray(len(graph))
    distance = [-1] * len(graph)
    order: list[int] = []
    queue = [start]
    visited[start] = 1
    distance[start] = 0
    while queue:
        vertex = queue.pop(0)
        order.append(vertex)
        next_distance = distance[vertex] + 1
        for neighbour in graph[vertex]:
            if not visited[neighbour]:
                visited[neighbour] = 1
                distance[neighbour] = next_distance
                queue.append(neighbour)
    return order, distance
def median_seconds(timer: timeit.Timer, repeat: int = 7) -> tuple[float, list[float]]:
    samples = timer.repeat(repeat=repeat, number=1)
    return statistics.median(samples), samples
def main() -> None:
    sizes = [500, 2_000, 8_000, 16_000]
    cases = []
    for size in sizes:
        graph = make_graph(size)
        expected_order, expected_distance = bfs_deque(graph, 0)
        list_order, list_distance = bfs_list_pop_zero(graph, 0)
        assert list_order == expected_order
        assert list_distance == expected_distance
        deque_timer = timeit.Timer(lambda: bfs_deque(graph, 0))
        list_timer = timeit.Timer(lambda: bfs_list_pop_zero(graph, 0))
        deque_median, deque_samples = median_seconds(deque_timer)
        list_median, list_samples = median_seconds(list_timer)
        cases.append(
            {
                "vertices": size,
                "edges": sum(map(len, graph)),
                "reachable": len(expected_order),
                "deque_median_ms": round(deque_median * 1000, 6),
                "list_pop_zero_median_ms": round(list_median * 1000, 6),
                "slowdown": round(list_median / deque_median, 3),
                "deque_samples_ms": [round(value * 1000, 6) for value in deque_samples],
                "list_pop_zero_samples_ms": [round(value * 1000, 6) for value in list_samples],
            }
        )
    output = {
        "python": sys.version.split()[0],
        "implementation": platform.python_implementation(),
        "platform": platform.platform(),
        "machine": platform.machine(),
        "seed": 20260930,
        "degree": 4,
        "repeat": 7,
        "correctness": "all deque and list.pop(0) traversals produced identical order and distances",
        "cases": cases,
    }
    print(json.dumps(output, indent=2))
if __name__ == "__main__":
    main()

python3 bfs_benchmark.py

$ python3 bfs_benchmark.py
{
  "python": "3.13.5",
  "implementation": "CPython",
  "platform": "Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41",
  "machine": "aarch64",
  "seed": 20260930,
  "degree": 4,
  "repeat": 7,
  "correctness": "all deque and list.pop(0) traversals produced identical order and distances",
  "cases": [
    {
      "vertices": 500,
      "edges": 2489,
      "reachable": 500,
      "deque_median_ms": 0.503052,
      "list_pop_zero_median_ms": 0.523903,
      "slowdown": 1.041,
      "deque_samples_ms": [
        0.590477,
        0.473997,
        0.48346,
        0.514756,
        0.518108,
        0.482423,
        0.503052
      ],
      "list_pop_zero_samples_ms": [
        0.557496,
        0.523903,
        0.595532,
        0.555274,
        0.512125,
        0.491237,
        0.48433
      ]
    },
    {
      "vertices": 2000,
      "edges": 9990,
      "reachable": 2000,
      "deque_median_ms": 2.848071,
      "list_pop_zero_median_ms": 3.963175,
      "slowdown": 1.392,
      "deque_samples_ms": [
        2.918293,
        2.940997,
        2.762702,
        2.848071,
        2.882108,
        2.402372,
        2.691147
      ],
      "list_pop_zero_samples_ms": [
        3.933749,
        3.989193,
        3.963175,
        4.69691,
        3.907489,
        3.811157,
        5.354683
      ]
    },
    {
      "vertices": 8000,
      "edges": 39987,
      "reachable": 8000,
      "deque_median_ms": 14.633726,
      "list_pop_zero_median_ms": 31.602601,
      "slowdown": 2.16,
      "deque_samples_ms": [
        15.009224,
        15.12913,
        14.606837,
        14.383358,
        14.633726,
        14.538486,
        14.738299
      ],
      "list_pop_zero_samples_ms": [
        30.675627,
        31.28166,
        30.550406,
        31.602601,
        31.784934,
        31.762878,
        33.927362
      ]
    },
    {
      "vertices": 16000,
      "edges": 79994,
      "reachable": 16000,
      "deque_median_ms": 30.627312,
      "list_pop_zero_median_ms": 93.694479,
      "slowdown": 3.059,
      "deque_samples_ms": [
        43.52631,
        43.585828,
        30.948736,
        30.627312,
        29.189619,
        26.967524,
        27.285652
      ],
      "list_pop_zero_samples_ms": [
        93.883422,
        93.565888,
        93.501165,
        93.694479,
        93.139631,
        93.991736,
        93.758182
      ]
    }
  ]
}
exit=0

The queue is part of the algorithm

Breadth-first search visits a graph in layers. It starts with one vertex, visits its unvisited neighbours, then visits the neighbours of those vertices. In an unweighted graph, that order gives the shortest path in edges from the start vertex to every reachable vertex.^[1]

The usual implementation keeps three pieces of state: a queue of vertices waiting to be processed, a visited marker, and a distance array. When a vertex enters the queue, it is marked immediately. That matters because a graph can offer the same vertex through several edges before the vertex reaches the front of the queue.

The algorithmic work is linear in the number of vertices and edges, O(V + E), when the graph is stored as adjacency lists and each vertex is enqueued once.^[1] The choice of queue does not change that graph-level bound. It can still change the cost of the Python program that implements it.

A breadth-first search panel shows a first-in, first-out queue visiting one layer before the next. A measured table compares deque with list.pop(0) at 500, 2,000, 8,000 and 16,000 vertices; the list version is 3.06 times slower at 16,000 vertices. — The left panel shows the BFS queue rule. The table reports median traversal time from seven samples for the two implementations on four seeded graph sizes; both returned identical traversal and distance arrays.

The small Python detail that changes the run time

A list is a poor FIFO queue. Python’s tutorial says that removing from the beginning is slow because the other elements must be shifted by one position.^[2] deque is the standard-library container intended for this job: its documentation describes fast appends and pops at either end.^[3]

The two functions in the benchmark do the same graph work. Their only meaningful difference is queue.pop(0) in the baseline and queue.popleft() in the replacement. Both mark a vertex when it is queued, so neither version performs duplicate traversal.

What the measurements show

The correctness check compared traversal order and shortest distances for every case. All four graph sizes matched exactly.

At 500 vertices, the queue operation is a small part of the run and the medians are close: 0.503 ms for deque and 0.524 ms for list.pop(0). At 2,000 vertices, the list version is 1.39 times slower. The ratio reaches 2.16 at 8,000 vertices and 3.06 at 16,000.

The gap is not a new BFS complexity theorem. It is the cost of repeatedly moving the live queue contents when the list’s front is removed. The queue can grow as a traversal fans out, so the amount of shifting depends on the shape of the particular graph as well as its vertex count.

timeit is used here because Python provides it specifically for timing small pieces of code and for repeating a timing run.^[4] The script stores every sample, reports the median, and leaves graph construction outside the timed callable. That makes the comparison narrower: it measures traversal and queue operations, not the cost of generating the input.

Where this comparison stops

The benchmark uses one seeded directed graph family, one start vertex, one degree setting, and CPython 3.13.5 on a Raspberry Pi with aarch64. It does not compare memory use, a recursive depth-first search, weighted shortest paths, or graphs whose vertices are discovered in a different pattern.

For an unweighted graph, the practical rule is simple. Use a queue, mark vertices when they enter it, and use deque when the queue must remove from the left. The asymptotic graph work remains O(V + E), while the implementation avoids paying for a front-shift on every visit.

Sources

[1] Breadth First Search – Algorithms for Competitive Programming

[2] Using Lists as Queues – Python 3.14 documentation

[3] collections.deque – Python 3.13 documentation

[4] timeit – Measure execution time of small code snippets – Python documentation