Breadth-first search (BFS)

Why it costs this much

Each vertex is enqueued once, and each edge is examined once when its endpoint is dequeued.

Code

from collections import deque
def bfs(graph, start):
    seen, q = {start}, deque([start])
    while q:
        u = q.popleft()               # each vertex leaves the queue once
        for v in graph[u]:            # each edge is scanned once overall
            if v not in seen:
                seen.add(v)           # mark on enqueue
                q.append(v)
    return seen

Common pitfalls

Mark vertices as visited when you enqueue them, not when you dequeue them, or duplicates flood the queue. With an adjacency matrix the cost is O(V²).

Operation by operation

Breadth-first search. Adjacency list. Stops early only if you return when the target is found. With an adjacency matrix, enumerating neighbors makes it O(V²).