Graphs: Representations, BFS vs DFS, and the Assumption Dijkstra Makes Silently

Two representations

An adjacency list stores, per vertex, the list of its neighbours: \(\Theta(V+E)\) space, iterating a vertex’s neighbours costs \(\Theta(\deg(u))\), and testing whether a specific edge exists costs \(\Theta(\deg(u))\). An adjacency matrix stores a \(V \times V\) array: \(\Theta(V^2)\) space, \(O(1)\) edge test, but \(\Theta(V)\) to walk one vertex’s neighbours — even if it has two.

Real graphs — social networks, road networks, citation graphs, molecules — are sparse, with \(E = O(V)\) rather than \(\Theta(V^2)\), so lists win by a wide margin: a million vertices in a matrix is \(10^{12}\) entries. The matrix earns its place when the graph is genuinely dense, when the inner loop is repeated edge queries, or when you want to do spectral work on it — eigenvectors of the graph Laplacian, and the message-passing layers built on them in the graph neural network book, operate on the matrix form (usually sparse-encoded).

BFS and DFS

Both visit every reachable vertex once and scan every incident edge once, so both are \(\Theta(V+E)\) with adjacency lists. The only structural difference is the frontier: a queue gives BFS, a stack gives DFS.

BFS dequeues vertices in non-decreasing distance from the source, which is exactly why it solves unweighted shortest paths. It also gives connected components, bipartiteness testing, and level-by-level structure.

from collections import deque

def bfs_shortest(adj, src, dst):
    """Fewest-edges path in an unweighted graph. Theta(V + E)."""
    if src == dst:
        return [src]
    prev = {src: None}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in prev:            # mark on ENQUEUE, never on dequeue
                prev[v] = u
                if v == dst:
                    path = [dst]
                    while prev[path[-1]] is not None:
                        path.append(prev[path[-1]])
                    return path[::-1]
                q.append(v)
    return None

adj = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": ["e"], "e": []}
print(bfs_shortest(adj, "a", "e"))   # ['a', 'b', 'd', 'e']

Marking a vertex when it is enqueued rather than when it is dequeued is not a detail: mark late and a vertex with several discovered predecessors enters the queue several times, and the cost stops being linear.

DFS goes deep first, and its recursion fits anything defined recursively on subgraphs: cycle detection (a back edge to a vertex still on the recursion stack), topological ordering, Tarjan’s strongly connected components, articulation points. Its depth is \(\Theta(V)\) worst case, so in Python a long path exhausts the call stack — write it iteratively for large graphs.

Topological sort

A topological order lists the vertices of a directed graph so that every edge points forwards. It exists if and only if the graph is a DAG. Kahn’s algorithm computes one in \(\Theta(V+E)\): compute in-degrees, seed a queue with the zero-in-degree vertices, and each time you emit a vertex decrement its successors’ in-degrees, enqueueing any that reach zero. If fewer than \(V\) vertices come out, the remainder contain a cycle — so the algorithm doubles as a cycle detector. This is how build systems order compilation, how spreadsheets order recalculation, and how an autograd engine orders the backward pass over its computation graph.

Shortest paths

Unweighted: BFS, \(\Theta(V+E)\). Do not reach for Dijkstra here; with unit weights BFS gives the same answer with no priority queue.

Non-negative weights: Dijkstra. Keep tentative distances in a priority queue; repeatedly extract the closest unfinalised vertex, declare its distance final, and relax its outgoing edges. With a binary heap and lazy deletion this is \(\Theta((V+E)\log V)\); a Fibonacci heap gives \(O(E + V\log V)\) in theory but loses on constants in practice.

The correctness argument is one sentence, and it contains the assumption: when \(u\) is extracted with the smallest tentative distance, no undiscovered route can beat it, because every remaining edge only adds weight. Delete that clause and the proof collapses.

Negative weights: Bellman–Ford, \(\Theta(VE)\), which relaxes all edges \(V-1\) times and reports a negative cycle if a \(V\)-th pass still improves something.

Union-find

Disjoint-set union maintains a partition under two operations: find(x) returns the representative of \(x\)’s set, union(a, b) merges two sets. With union by size (hang the smaller tree under the larger) and path compression (re-point nodes at the root during find), \(m\) operations on \(n\) elements cost \(O(m\,\alpha(n))\) amortised, where \(\alpha\) is the inverse Ackermann function — below 5 for any \(n\) that fits in the universe.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                   # already together
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

d = DSU(5)
d.union(0, 1); d.union(3, 4)
print(d.find(0) == d.find(1))   # True
print(d.find(0) == d.find(3))   # False

Use it for Kruskal’s minimum spanning tree, for streaming connected components, and for near-duplicate clustering — anywhere edges arrive online and you only ever ask “same component?”. It cannot un-merge, and it cannot give you a path.

References

1. Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271, 1959.
2. Kahn, A. B. Topological sorting of large networks. Communications of the ACM 5(11), 558–562, 1962.
3. Tarjan, R. E. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22(2), 215–225, 1975.
4. Fredman, M. L., & Tarjan, R. E. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596–615, 1987.
5. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022 — part VI on graph algorithms.
6. Sedgewick, R., & Wayne, K. Algorithms, 4th ed. — graph chapter with runnable code.