Graphs §

Adjacency list: an array of lists (or vectors). Best for sparse graphs ($m \ll n^2$). The standard choice for most algorithms. Each list is a List structure.

Adjacency matrix: a 2D boolean array. Best for dense graphs or when edge queries are frequent. Supports fast matrix multiplication for transitive closure: the naive algorithm is $O(n^3)$; Strassen’s divide-and-conquer gives $O(n^{\log_2 7}) \approx O(n^{2.807})$; the best-known algorithms achieve $O(n^{\omega})$ with $\omega < 2.373$.

Edge list: a flat array of (u, v, weight) tuples. Compact, good for external-memory algorithms and GPU parallelism.

Complexity context: the Big-O bounds above are analyzed in the framework of Computability and Complexity Classes, which defines time and space complexity and complexity classes.

BFS: maintain a queue. Start from source $s$, mark visited, enqueue neighbors. The first time a vertex is dequeued, the path to it is shortest (in edge count).

Worked example — BFS on a 6-node graph:

Consider the undirected graph with edges: 0-1, 0-2, 1-3, 2-4, 3-4, 4-5. Start from node 0.

The BFS levels are:

DFS: maintain a stack (or call stack). Three states per vertex: white (unvisited), gray (in progress), black (done). A back edge (to a gray vertex) indicates a cycle in a directed graph; in an undirected graph, any edge to an already-visited vertex that is not the parent indicates a cycle.

Topological sort (Kahn’s algorithm): repeatedly remove vertices with in-degree 0. $O(n + m)$. Fails (detects a cycle) if not all vertices are removed. Used in build systems (make, Bazel), dependency resolution (npm, cargo), and course scheduling.

Interactive visualization: see the Graphs simulation for animated BFS, DFS, and Dijkstra.

Dijkstra: maintain a priority queue of (distance, vertex). Pop the minimum, relax its outgoing edges. Each vertex is finalized once. The binary heap gives $O(\log n)$ per extract-min and $O(\log n)$ per decrease-key.

Worked example — Dijkstra on a 5-node weighted graph:

Edges: A→B (4), A→C (2), B→C (1), B→D (5), C→D (8), C→E (10), D→E (2). Source: A.

Shortest distances from A: d(A)=0, d(B)=3, d(C)=2, d(D)=8, d(E)=10.

Floyd-Warshall: all-pairs shortest paths in $O(n^3)$. Dynamic programming over the set of allowed intermediate vertices.

A*: the heuristic $h(v)$ estimates the remaining cost to the target. In a grid, Manhattan distance is admissible. In a road network, the crow-fly (Euclidean) distance is admissible. A* is the basis of GPS navigation and game pathfinding.

See also Learning Paradigms and Models for the RL framing of shortest-path problems.

Union-Find (disjoint set union): supports make-set, find, union in $O(\alpha(n))$ amortized per operation (inverse Ackermann, effectively constant). Path compression + union by rank.

Cut property: for any cut of the graph, the minimum-weight edge crossing the cut is in some MST. Both Kruskal and Prim exploit this property.

Worked example — Kruskal on a 6-node weighted graph:

Edges (sorted by weight): AB(1), BC(2), CD(3), DE(4), EF(5), AC(6), BE(7), DF(8).

MST edges: AB, BC, CD, DE, EF. Total weight: 1+2+3+4+5 = 15.

Applications: network design (minimize cable length), clustering (single-linkage), image segmentation (minimum spanning tree of a pixel graph), and approximation algorithms (Christofides: MST gives a 1.5-approximation for TSP).

Residual graph: after pushing flow, the residual graph has forward edges with residual capacity $c(u,v) - f(u,v)$ and backward edges with capacity $f(u,v)$ (allowing “undo”). An augmenting path is any $s \to t$ path in the residual graph.

Worked example — Ford-Fulkerson on a small network:

Nodes: s, a, b, t. Edges and capacities: s→a (3), s→b (2), a→b (1), a→t (2), b→t (3).

No more augmenting paths exist. Max flow = 2 + 2 + 1 = 5.

The min cut is $S = \{s, a, b\}$, $T = \{t\}$: capacity = c(a,t) + c(b,t) = 2 + 3 = 5. ✓

Applications:

• Bipartite matching: reduce to max-flow by adding a source connected to the left partition and a sink from the right partition, all with capacity 1.
• Image segmentation: the min-cut of a graph whose nodes are pixels and whose edge weights encode color similarity separates foreground from background (graph cuts).
• Project scheduling: the critical path in a project network is the longest path; the dual (min-cut) identifies the set of tasks whose delay would extend the project.
• Transportation: maximize throughput in a road or pipe network.

Choice: Dijkstra’s algorithm with a binary heap.

Reasoning:

1. All weights are positive → Dijkstra applies (Bellman-Ford is unnecessary).
2. The graph is sparse: $m = 2000 \ll n^2 = 250{,}000$ → adjacency list representation.
3. Time: $O((n + m) \log n) = O(2500 \cdot \log 500) \approx 22{,}500$ operations.
4. A* would be faster in practice if a good admissible heuristic is available (e.g., geographic distance for a road network), but without domain-specific structure, Dijkstra is the safe default.
5. Floyd-Warshall ($O(n^3) = 125{,}000{,}000$) is overkill for a single-source query.

If weights could be negative: switch to Bellman-Ford, $O(nm) = 1{,}000{,}000$ operations.

If the graph were undirected and unweighted: BFS in $O(n + m) = 2500$ operations.