Python graph BFS: mark a vertex when it enters the queue

Operation contract

The route fixture uses deque for endpoint queue operations and records a vertex’s distance when it is enqueued. Two routes may reach the same neighbor, but only the first enqueues it. Unreachable vertices keep distance negative one. The graph uses explicit numbered vertices rather than assuming labels correspond to list positions accidentally.

Failure and ownership boundary

The contract validates vertex count and neighbor indices, then searches one connected reachability region. It is not a weighted shortest-path algorithm; edge weights require a different rule. Python sets: membership and deduplication do not preserve input order and Java breadth-first search: shortest unweighted distances provide related state choices, while the graph input remains a prebuilt adjacency list.

Working program

from collections import deque

def route_distances(graph, start):
    if type(start) is not int or not 1 <= len(graph) <= 1000 or not 0 <= start < len(graph):
        raise ValueError("graph bounds")
    if sum(map(len, graph)) > 10000 or any(type(vertex) is not int or not 0 <= vertex < len(graph) for row in graph for vertex in row):
        raise ValueError("edge bounds")
    distance = [-1] * len(graph)
    distance[start] = 0
    pending = deque([start])
    while pending:
        current = pending.popleft()
        for neighbor in graph[current]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[current] + 1
                pending.append(neighbor)
    return distance

print(route_distances([[1, 2], [3], [3], [], []], 0))

Output

[0, 1, 1, 2, -1]

Costs and limits

Validation and traversal take O(v+e) time for v vertices and e adjacency entries. Distances and the queue retain O(v) additional state, excluding the supplied graph.

Common Mistakes

• Mark a vertex on enqueue, not after repeated queue insertion.
• BFS edge count is not a weighted route cost.

Connected lessons

Python sets: membership and deduplication do not preserve input order, Python lists: slicing copies the outer sequence, not nested objects, Java breadth-first search: shortest unweighted distances.

Apply this boundary

Python Dijkstra: nonnegative weights and stale heap entries, Python topological sort: dependency order and cycle rejection, Python iterative tree traversal: shared nodes are not a tree.

Check the next state boundary

Python graph bridges: track edge identity when parallel links are allowed, Python strongly connected components: partition a directed dependency graph.

Follow the ownership and update boundary

Python bipartite matching: augment an assignment instead of taking the first free slot.