Complexity

The cost of a graph traversal depends on the number of vertices V, the number of edges E, and how the graph is stored. This chapter analyzes time and space for BFS, DFS and topological sorting, and compares representations and alternative algorithms.

Why O(V + E)

Running BFS or DFS on an adjacency list, two facts hold:

• Thanks to the visited marker, each vertex enters the queue (or stack) once and leaves once. That is the O(V) part.
• When a vertex is processed, its neighbor list is scanned once. The neighbor lists add up to E entries in a directed graph and 2E in an undirected one. That is the O(E) part.

So the total is O(V + E). There is no separate best, average or worst case: a full traversal always pays this for the reachable part of the graph. Only an early exit, such as stopping when a target is found, can finish sooner.

With an adjacency matrix, finding a vertex's neighbors means scanning its whole row of V cells, so the traversal becomes O(V^2). For sparse graphs that is a big difference.

from collections import deque

def bfs_matrix(matrix, start):
    n = len(matrix)
    dist = [-1] * n
    dist[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in range(n):               # scans all n cells, neighbor or not
            if matrix[u][v] and dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist                          # O(V^2) overall

Space

• Visited, distance and parent arrays: O(V)
• BFS queue: up to a whole layer, so O(V) in the worst case
• DFS stack or recursion depth: O(V) in the worst case (a long chain)
• The graph itself: O(V + E) as an adjacency list, O(V^2) as a matrix

Representations compared

For dense graphs, where E approaches V^2 (say a thousand vertices and hundreds of thousands of edges), a matrix is reasonable. Most real-world and interview graphs are sparse, so the adjacency list is the default. If you frequently ask "are u and v adjacent?", store neighbors in a set instead of a list for average O(1) lookups.

Grid graphs

An R x C grid has RC vertices and at most four neighbors per cell, so O(RC) edges. Grid BFS takes O(RC) time and space. A 1000 x 1000 grid is a million vertices, and in Python constant factors start to matter: flattening coordinates to a single index (r * C + c) and using flat lists noticeably speeds things up.

Compared with other algorithms

When every edge has the same weight, BFS is both simpler and faster than Dijkstra.

Mistakes that inflate the constant

Using a list as a queue makes each pop(0) shift every remaining element, turning BFS into O(V^2).

from collections import deque
import timeit

def drain_list(n):
    items = list(range(n))
    while items:
        items.pop(0)          # O(n) each time

def drain_deque(n):
    items = deque(range(n))
    while items:
        items.popleft()       # O(1) each time

n = 100_000
print(timeit.timeit(lambda: drain_list(n), number=1))
print(timeit.timeit(lambda: drain_deque(n), number=1))

Recursive DFS raises RecursionError once it passes Python's recursion limit (about 1000 by default). You can raise the limit, but overflowing the C stack can crash the process, so deep graphs are safer with an iterative DFS.

import sys

def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)

print(sys.getrecursionlimit())   # usually 1000
try:
    depth(5000)
except RecursionError:
    print("Recursion too deep; switch to an iterative DFS.")

Summary

BFS, DFS and topological sorting on an adjacency list all run in O(V + E) time with O(V) extra space. An adjacency matrix makes edge checks instant but traversal O(V^2). In practice, implementation choices such as using a deque and avoiding deep recursion matter as much as the asymptotics.