Graphs
Graphs model relationships. Social networks, road maps, dependency chains, internet routing, circuit design — if there are entities with connections between them, there is a graph. Graph algorithms are among the most practically important in all of computer science, and they appear frequently in interviews at every level.
This page is the overview lesson of Module 4 — Graphs in DSA: Zero to Mastery, and it is also the module's landing page. It gives you the vocabulary, the three representations, the two traversals (BFS and DFS), the classic shortest-path algorithms, topological sorting, strongly connected components, Union-Find and Kruskal's minimum spanning tree — each one traced by hand on a small graph, proved correct, and implemented in Python, Java, C++ and TypeScript. Every section ends with a pointer to the lesson that goes deeper.
How this module is organised
Module 4 has one overview (this page), thirteen deep lessons and a capstone. The order is deliberate: first how to turn a problem into a graph, then the two ways to walk one, then what those walks compute (orderings, distances, components), then the optimisation problems built on top (spanning trees, matchings, flows), and finally where all of it runs in real systems.
| # | Lesson | What you will be able to do | Minutes |
|---|---|---|---|
| 1 | Graphs (Overview) | Name the parts of a graph, pick a representation, and run BFS, DFS, Dijkstra, Kahn and Union-Find by hand. | 50 |
| 2 | Graph Modeling & Implicit Graphs | Turn grids, word puzzles, game states and dependency lists into vertices and edges without building them explicitly. | 40 |
| 3 | BFS in Depth | Find unweighted shortest paths, run multi-source, 0-1 and bidirectional BFS, and reconstruct paths. | 50 |
| 4 | DFS in Depth | Classify edges, detect cycles, use discovery/finish times, and convert recursion to an explicit stack. | 50 |
| 5 | Topological Sort & DAG DP | Order dependencies with Kahn or DFS, detect cycles, and compute longest paths and path counts on a DAG. | 45 |
| 6 | Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson & A* | Choose and prove the right shortest-path algorithm for the weights you have, including negative cycles and heuristics. | 75 |
| 7 | Union-Find in Depth | Implement DSU with rank and path compression, explain the inverse-Ackermann bound, and use rollback and weighted variants. | 50 |
| 8 | Minimum Spanning Trees: Kruskal, Prim & Boruvka | Prove the cut and cycle properties and build an MST three ways. | 50 |
| 9 | Connectivity: Bridges, Articulation Points, SCCs & Condensation | Find single points of failure with low-link values and collapse a digraph into its DAG of SCCs. | 60 |
| 10 | Euler & Hamiltonian Paths | Find an Euler path in linear time with Hierholzer, and solve small Hamiltonian problems with bitmask DP. | 45 |
| 11 | Bipartite Graphs, Matching & the Hungarian Algorithm | Two-colour a graph, find maximum matchings with augmenting paths, and solve assignment problems. | 55 |
| 12 | Network Flow: Ford-Fulkerson, Edmonds-Karp, Dinic & Min-Cost Flow | Compute max flow and min cut, and model scheduling and selection problems as flow. | 75 |
| 13 | 2-SAT, Graph Coloring & Other Classic Graph Problems | Solve 2-SAT through implication graphs and recognise which colouring and clique problems are NP-hard. | 50 |
| 14 | Graph Algorithms in the Real World | Explain how PageRank, OSPF and BGP routing, build systems and social graphs use the algorithms above. | 45 |
| 15 | Capstone: Dijkstra on a Real Road Network | Load a road network, run Dijkstra and A* between coordinates, compare work done, and print turn-by-turn directions. | 240 |
flowchart LR
OV["Graphs overview"] --> GM["Graph modeling"]
GM --> BFS["BFS in depth"]
BFS --> DFS["DFS in depth"]
DFS --> TOPO["Topological sort and DAG DP"]
TOPO --> SP["Shortest paths"]
SP --> UF["Union-Find"]
UF --> MST["Minimum spanning trees"]
MST --> CON["Connectivity and SCCs"]
CON --> EUL["Euler and Hamiltonian paths"]
EUL --> BIP["Bipartite matching"]
BIP --> FLOW["Network flow"]
FLOW --> SAT["2-SAT and colouring"]
SAT --> RW["Graphs in the real world"]
RW --> CAP["Capstone: road-network Dijkstra"]
The whole module is about 12 hours of reading plus the capstone. The minutes column is reading-and-tracing time; the practice ladders roughly double it.
Module 4 at a glance
A graph is a set of things (vertices) and a set of pairwise connections between them (edges). That is the most general structure in this course: an array is a path graph, a linked list is a path graph with pointers, a tree is a connected graph without cycles, and a heap is a tree with an extra ordering rule. Graphs drop every one of those restrictions. Edges may form cycles, point one way only, carry weights, or be absent altogether, and vertices may have any number of neighbours. That generality is why graph algorithms show up everywhere from compilers to routers — and why they are harder: on a tree, recursion never revisits a node, but on a graph it will, forever, unless you remember where you have been.
The module is in the DSA: Zero to Mastery course. Previous module: Module 3 · Trees, which ends with Capstone: A Range-Query Engine. Next: Module 5 (recursion, backtracking and greedy).
What this module covers
Thirteen lessons and a capstone after this overview, in four arcs.
Arc 1 — modelling and traversal. Graph Modeling & Implicit Graphs is about the step that interviews actually test: noticing that a word puzzle, a lock combination or a grid of pixels is a graph. BFS in Depth and DFS in Depth then give you the two traversals and everything they compute directly: distances, components, bipartiteness, cycles, discovery and finish times.
Arc 2 — what traversals compute. Topological Sort & DAG DP orders a dependency graph and runs dynamic programming along that order. Shortest Paths is the whole family — Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson's reweighting and A* — with proofs and the exact conditions under which each one is correct.
Arc 3 — components and trees. Union-Find in Depth maintains connected components under edge insertions in near-constant time. Minimum Spanning Trees uses it (Kruskal) or a heap (Prim). Connectivity finds bridges, articulation points and strongly connected components with Tarjan's low-link idea, and builds the condensation DAG that turns any directed graph into a topological-sort problem.
Arc 4 — classic hard-looking problems. Euler & Hamiltonian Paths contrasts a linear-time problem with an NP-hard one that looks almost identical. Bipartite Matching and Network Flow are the most powerful modelling tools in the module: a surprising number of scheduling, assignment and selection problems become a max-flow computation. 2-SAT & Coloring shows where polynomial time ends. Graph Algorithms in the Real World ties it together with PageRank, routing protocols, package managers and graph databases.
Capstone. Capstone: Dijkstra on a Real Road Network: load a road graph (OpenStreetMap or the DIMACS challenge graphs; an offline synthetic city ships with the reference), run Dijkstra and A* between coordinates, measure how many vertices each expands, and print turn-by-turn directions.
Optional deep dives. Greedy Algorithms has a second treatment of MSTs, and Advanced Data Structures a second treatment of DSU.
Why in this order
Modelling comes first because most failed graph interviews fail before any algorithm runs: the candidate does not see the graph. Once you can see vertices and edges, BFS comes before DFS because BFS has the simpler invariant (a queue ordered by distance) and answers the most common question (fewest steps). DFS follows because its finish times power the next three lessons: topological sort is "reverse finish order", cycle detection is "an edge to a vertex still on the stack", and Kosaraju and Tarjan are DFS with bookkeeping.
Shortest paths sit after topological sort because the DAG shortest-path algorithm (relax edges in topological order) is the cleanest possible example of relaxation, and Dijkstra and Bellman-Ford are best understood as ways of finding a good relaxation order when no topological order exists. Union-Find comes before MSTs because Kruskal is a loop around it. Connectivity needs DFS finish times and low-links, so it comes after the DFS lesson and after enough practice that the bookkeeping does not obscure the idea. Matching and flow come last among the algorithms because they need BFS (Edmonds-Karp, Hopcroft-Karp), DFS (augmenting paths) and the min-cut duality all at once.
flowchart TD
M3["Module 3 · Trees"] --> OV["Graphs overview"]
OV --> GM["Graph modeling"]
GM --> BFS["BFS"]
GM --> DFS["DFS"]
DFS --> TOPO["Topological sort"]
BFS --> SP["Shortest paths"]
TOPO --> SP
OV --> UF["Union-Find"]
UF --> MST["MST"]
SP --> MST
DFS --> CON["Connectivity and SCCs"]
DFS --> EUL["Euler paths"]
BFS --> BIP["Bipartite matching"]
BIP --> FLOW["Network flow"]
CON --> SAT["2-SAT"]
SP --> RW["Real world"]
FLOW --> RW
SP --> CAP["Capstone"]
Arrows mean "read this first". Union-Find does not depend on the traversals and can be read any time after this overview; Euler paths and 2-SAT can be read in either order once DFS and connectivity are done.
Prerequisites
From Module 0: Complexity Analysis — graph bounds are stated in two variables, and , and you need to be comfortable with versus — and Recursion & Mathematical Induction, because DFS is recursion and most proofs below are inductions on distance or on the number of processed vertices. From Module 1: Queues, Deques & Circular Buffers (BFS and 0-1 BFS), Stacks (iterative DFS) and Matrices & Grids (grids are the most common implicit graph). From Module 3: Heaps & Priority Queues (Dijkstra, Prim) and the tree traversals — a tree is a graph, and BFS and DFS on a graph are the tree traversals plus a visited set.
You need one of Python 3.12+, Java 21, C++20 or TypeScript (Node 22+). Every canonical implementation here is given in all four, uses the same small test graphs, and checks itself with asserts.
How to study this module
Draw the graph, then trace. Every algorithm on this page comes with a trace table computed by a script. Draw the example graph on paper, run the algorithm yourself, and only then compare with the table. Graph bugs are almost always state bugs — a vertex marked visited too late, a queue entry that is stale — and those are visible in a trace long before they are visible in a debugger.
Say the invariant out loud. BFS: "the queue holds vertices in non-decreasing distance order". Dijkstra: "every vertex popped for the first time has its final distance". Kahn: "every vertex in the output has all its predecessors before it". If you can state the invariant, you can write the code and defend it in an interview.
Test on five graphs. An empty graph or single vertex, a disconnected graph, a graph with a cycle, a long path (100,000 vertices — it breaks recursive DFS in Python and Java with default stacks), and a dense graph. Most bugs live in the disconnected case ("I only started from vertex 0") and the long path.
Model before you code. For each practice problem, write one line first: "vertices are …, edges are …, weights are …, the question is reachability / distance / ordering / components". The modelling lesson is built around this habit.
Climb the practice ladder in two passes. Problems 1–10 below as you read this page; 11–15 after the deep lessons on shortest paths and connectivity.
Start here, then follow the table. Previous module: Trees. Course map: DSA: Zero to Mastery.
Why graphs exist
The subject starts with a puzzle. In 1736 Leonhard Euler was asked whether one could walk through the city of Königsberg crossing each of its seven bridges exactly once. He threw away everything irrelevant — the shape of the land, the length of the bridges — and kept only which land masses were connected by which bridges. In that abstraction the answer is obvious: a walk that uses every edge once must enter and leave every intermediate land mass equally often, so at most two land masses may have an odd number of bridges, and Königsberg had four. That act of abstraction is the whole discipline: a graph keeps only the connections, and the connections are usually what the question is about.
The algorithms on this page were mostly invented between 1956 and 1975, when computers made it practical to ask questions about graphs with thousands of vertices. Edsger Dijkstra designed his shortest-path algorithm in 1956 (published 1959) to demonstrate the ARMAC computer on a map of Dutch cities; Richard Bellman (1958) and Lester Ford (1956) gave the relaxation algorithm that handles negative weights; Robert Floyd and Stephen Warshall published all-pairs algorithms in 1962; Arthur Kahn published his topological sort for scheduling PERT networks in 1962; Joseph Kruskal (1956) and Robert Prim (1957, rediscovering Vojtěch Jarník's 1930 algorithm) solved the minimum spanning tree problem; Bernard Galler and Michael Fischer introduced the disjoint-set forest in 1964; and Robert Tarjan's work from 1972 to 1975 put depth-first search at the centre of the field and proved the inverse-Ackermann bound for Union-Find.
Today the same algorithms run inside infrastructure you use every day. A router running OSPF executes Dijkstra on the link-state database every time the topology changes. Your build tool topologically sorts the dependency graph before compiling anything. A garbage collector's mark phase is a graph traversal from the roots. A spreadsheet recomputes cells in topological order and reports a "circular reference" when DFS finds a back edge. A database's deadlock detector looks for a cycle in the wait-for graph. Knowing these algorithms is not interview trivia; it is knowing how the systems under your code work.
Pattern triggers
The literal signals in a problem statement, and the first thing to reach for. Most graph problems do not use the word "graph".
| If the problem says or has… | Think of… |
|---|---|
| "minimum number of steps / moves / transformations", every step costs the same | BFS from the start (or from all starts at once) |
| a grid of cells with walls, "islands", "regions", "flood fill" | BFS or DFS on the implicit grid graph; count components |
| "shortest path" with positive weights, "minimum cost", "network delay" | Dijkstra with a binary heap |
| edge weights only 0 or 1 ("free moves" and "paid moves") | 0-1 BFS with a deque |
| negative weights, "detect arbitrage", "at most k edges" | Bellman-Ford (k rounds for at most k edges) |
| "distance between every pair", or so | Floyd-Warshall |
| "prerequisites", "dependencies", "order of tasks", "build order", "can all courses be finished?" | Topological sort (Kahn); a leftover vertex means a cycle |
| "is there a cycle?" in a directed graph | DFS with three colours (back edge) or Kahn's leftover count |
| "is there a cycle?" / "redundant edge" in an undirected graph | Union-Find: an edge whose endpoints already share a root |
| "are these connected?", "number of groups", edges arrive over time | Union-Find (online) or BFS/DFS (offline) |
| "split into two groups with no conflict inside a group" | Bipartite check by two-colouring |
| "connect everything at minimum total cost" | Minimum spanning tree (Kruskal or Prim) |
| "mutually reachable", "groups where everyone can reach everyone" | Strongly connected components (Kosaraju or Tarjan) |
| "which single link or server, if removed, disconnects…" | Bridges / articulation points (connectivity lesson) |
| "assign workers to jobs", "maximum pairs" | Bipartite matching (matching lesson) |
| "maximum throughput", "minimum cut to separate" | Max flow / min cut (flow lesson) |
| a word list where words differ by one letter, a lock with dials, a puzzle state | Implicit graph + BFS (modelling lesson) |
| "use every edge exactly once" | Euler path (degree parity + Hierholzer) |
Two meta-triggers. If the input is a list of pairs (a, b), it is an edge list: build an adjacency list first. If the input size is , the intended solution is or better — anything quadratic in will time out.
Vocabulary
The words you need, defined once. A graph is written ; by convention and also denote the numbers of vertices and edges, so "" means linear in the size of the graph.
| Term | Meaning |
|---|---|
| Vertex (node) | One of the things. Usually numbered so they can index arrays. |
| Edge | A connection . Undirected: usable both ways. Directed (an arc): from to only. |
| Weight | A number on an edge: length, cost, time, capacity. Unweighted means every edge counts 1. |
| Degree | Number of edges at a vertex; in a digraph, in-degree and out-degree separately. |
| Path | A sequence of vertices joined by edges. Simple: no repeated vertex. Its length is the number of edges, or the sum of weights. |
| Cycle | A path that returns to its start. A self-loop is a cycle of length 1. |
| DAG | Directed acyclic graph: directed, with no directed cycle. Dependency graphs are DAGs. |
| Connected | Undirected: every vertex reaches every other. A connected component is a maximal connected piece. |
| Strongly connected | Directed: every vertex reaches every other following arrow directions. |
| Sparse / dense | Sparse: is close to (roads, social graphs). Dense: is close to . |
| Tree | A connected undirected graph with no cycle; it has exactly edges. A forest is a set of trees. |
| Bipartite | Vertices split into two sides with every edge crossing between them. |
Three counting facts are used constantly. A simple undirected graph has at most edges and a simple digraph at most , so and — which is why and are the same bound. The handshake lemma: in an undirected graph the degrees sum to , because every edge contributes 1 to the degree of each endpoint; so an adjacency list for an undirected graph has exactly entries, and the number of odd-degree vertices is even. And a connected graph with vertices has at least edges, with equality exactly when it is a tree.
Representations
How the graph sits in memory decides the complexity of everything that runs on it. There are three standard layouts and one non-layout.
Adjacency List
Each vertex stores a list of its neighbors. Best for sparse graphs ().
graph LR
0 --> 1
0 --> 2
1 --> 2
1 --> 3
2 --> 3
3 --> 4
This six-edge graph, [(0,1), (0,2), (1,2), (1,3), (2,3), (3,4)], is the running example for BFS and DFS below. Read as directed, vertex 1's list is [2, 3]; read as undirected, vertex 3's list is [1, 2, 4].
TypeScript:
// Unweighted adjacency list
type AdjList = Map<number, number[]>;
function buildAdjList(edges: [number, number][], directed = false): AdjList {
const graph: AdjList = new Map();
for (const [u, v] of edges) {
if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u)!.push(v);
if (!directed) graph.get(v)!.push(u);
}
return graph;
}
// Weighted adjacency list
type WeightedAdjList = Map<number, [number, number][]>; // [neighbor, weight]
Python:
from collections import defaultdict
def build_adj_list(edges: list[tuple[int, int]], directed=False) -> dict[int, list[int]]:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
# Weighted: graph[u] = [(v, weight), ...]
The same builder in all four languages, with the weighted variant and asserts on the running example. In Java and C++ the idiomatic layout is a vector of vectors indexed by vertex number, which is faster than a hash map and is what competitive and production code both use when vertices are dense integers.
from collections import defaultdict
def build_adj_list(edges: list[tuple[int, int]], directed=False) -> dict[int, list[int]]:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
# Weighted: graph[u] = [(v, weight), ...]
def build_weighted(edges: list[tuple[int, int, int]], directed=False) -> dict[int, list[tuple[int, int]]]:
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
if not directed:
graph[v].append((u, w))
return graph
EDGES = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]
und = build_adj_list(EDGES)
assert und[2] == [0, 1, 3] and und[3] == [1, 2, 4]
assert sum(len(nbrs) for nbrs in und.values()) == 2 * len(EDGES) # handshake lemma
dig = build_adj_list(EDGES, directed=True)
assert dig[1] == [2, 3] and dig.get(4, []) == []
wg = build_weighted([(0, 1, 4), (0, 2, 1)], directed=True)
assert wg[0] == [(1, 4), (2, 1)]
print("ok")
import java.util.ArrayList;
import java.util.List;
public class AdjacencyList {
record Edge(int to, int weight) {}
static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
List<List<Integer>> g = new ArrayList<>(n);
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) {
g.get(e[0]).add(e[1]);
if (!directed) g.get(e[1]).add(e[0]);
}
return g;
}
static List<List<Edge>> buildWeighted(int n, int[][] edges, boolean directed) {
List<List<Edge>> g = new ArrayList<>(n);
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) {
g.get(e[0]).add(new Edge(e[1], e[2]));
if (!directed) g.get(e[1]).add(new Edge(e[0], e[2]));
}
return g;
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {3, 4}};
List<List<Integer>> und = build(5, edges, false);
check(und.get(2).equals(List.of(0, 1, 3)) && und.get(3).equals(List.of(1, 2, 4)));
int total = 0;
for (List<Integer> nbrs : und) total += nbrs.size();
check(total == 2 * edges.length); // handshake lemma
List<List<Integer>> dig = build(5, edges, true);
check(dig.get(1).equals(List.of(2, 3)) && dig.get(4).isEmpty());
List<List<Edge>> wg = buildWeighted(3, new int[][] {{0, 1, 4}, {0, 2, 1}}, true);
check(wg.get(0).equals(List.of(new Edge(1, 4), new Edge(2, 1))));
System.out.println("ok");
}
}
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
using Graph = std::vector<std::vector<int>>;
using WGraph = std::vector<std::vector<std::pair<int, int>>>; // (neighbor, weight)
Graph build(int n, const std::vector<std::pair<int, int>>& edges, bool directed) {
Graph g(n);
for (auto [u, v] : edges) {
g[u].push_back(v);
if (!directed) g[v].push_back(u);
}
return g;
}
WGraph buildWeighted(int n, const std::vector<std::vector<int>>& edges, bool directed) {
WGraph g(n);
for (const auto& e : edges) {
g[e[0]].push_back({e[1], e[2]});
if (!directed) g[e[1]].push_back({e[0], e[2]});
}
return g;
}
int main() {
std::vector<std::pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {3, 4}};
Graph und = build(5, edges, false);
assert((und[2] == std::vector<int>{0, 1, 3}) && (und[3] == std::vector<int>{1, 2, 4}));
std::size_t total = 0;
for (const auto& nbrs : und) total += nbrs.size();
assert(total == 2 * edges.size()); // handshake lemma
Graph dig = build(5, edges, true);
assert((dig[1] == std::vector<int>{2, 3}) && dig[4].empty());
WGraph wg = buildWeighted(3, {{0, 1, 4}, {0, 2, 1}}, true);
assert((wg[0] == std::vector<std::pair<int, int>>{{1, 4}, {2, 1}}));
std::cout << "ok\n";
}
// Unweighted adjacency list
type AdjList = Map<number, number[]>;
function buildAdjList(edges: [number, number][], directed = false): AdjList {
const graph: AdjList = new Map();
for (const [u, v] of edges) {
if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u)!.push(v);
if (!directed) graph.get(v)!.push(u);
}
return graph;
}
// Weighted adjacency list
type WeightedAdjList = Map<number, [number, number][]>; // [neighbor, weight]
function buildWeighted(edges: [number, number, number][], directed = false): WeightedAdjList {
const graph: WeightedAdjList = new Map();
for (const [u, v, w] of edges) {
if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u)!.push([v, w]);
if (!directed) graph.get(v)!.push([u, w]);
}
return graph;
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
const EDGES: [number, number][] = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 3], [3, 4]];
const und = buildAdjList(EDGES);
if (!same(und.get(2), [0, 1, 3]) || !same(und.get(3), [1, 2, 4])) throw new Error("undirected lists");
let total = 0;
for (const nbrs of und.values()) total += nbrs.length;
if (total !== 2 * EDGES.length) throw new Error("handshake lemma");
const dig = buildAdjList(EDGES, true);
if (!same(dig.get(1), [2, 3]) || !same(dig.get(4), [])) throw new Error("directed lists");
const wg = buildWeighted([[0, 1, 4], [0, 2, 1]], true);
if (!same(wg.get(0), [[1, 4], [2, 1]])) throw new Error("weighted");
console.log("ok");
Note the asymmetry in the directed case: Python's defaultdict never creates a key for a vertex with no outgoing edges (vertex 4 here), while the TypeScript builder creates an empty list for every endpoint. Code that iterates graph.keys() to find all vertices silently skips sink vertices in the Python version. When vertices are , pass and allocate lists, as the Java and C++ versions do.
Adjacency Matrix
A matrix where matrix[i][j] indicates an edge from to . Best for dense graphs or when you need edge lookup.
Python:
def build_adj_matrix(n: int, edges: list[tuple[int, int]], directed=False) -> list[list[int]]:
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
if not directed:
matrix[v][u] = 1
return matrix
The same function with a self-check on the running example:
def build_adj_matrix(n: int, edges: list[tuple[int, int]], directed=False) -> list[list[int]]:
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
if not directed:
matrix[v][u] = 1
return matrix
EDGES = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]
m = build_adj_matrix(5, EDGES)
assert m[3] == [0, 1, 1, 0, 1] # row 3 = neighbours of 3
assert all(m[i][j] == m[j][i] for i in range(5) for j in range(5)) # undirected => symmetric
assert sum(map(sum, m)) == 2 * len(EDGES)
d = build_adj_matrix(5, EDGES, directed=True)
assert d[1][3] == 1 and d[3][1] == 0
print("ok")
The cost is space. With vertices a matrix has cells — 10 GB even at one byte per cell, 1.25 GB as a bitset — while a road network of that size has only a few hundred thousand edges. Matrices win when is a few thousand at most and you either need constant-time "is there an edge?" queries or the algorithm is inherently or anyway (Floyd-Warshall, dense Prim). Matrix powers also have a meaning: entry of counts the walks of exactly edges from to .
Edge list, CSR and implicit graphs
An edge list is just the array of (u, v, w) triples. It is the natural input format and the right structure for algorithms that look at every edge without caring which vertex it hangs off: Bellman-Ford loops over it times, and Kruskal sorts it.
Compressed sparse row (CSR) packs an adjacency list into two flat arrays: offsets of length and targets of length , where vertex 's neighbours are targets[offsets[u] : offsets[u+1]]. It uses about bytes with 32-bit integers, has no per-list allocation overhead, and scans neighbours as one contiguous memory run, which is why graph libraries, sparse-matrix code and road-routing engines use it for static graphs. You build it with a counting pass (out-degrees, then prefix sums — the same idea as counting sort).
An implicit graph is never stored at all. A grid's neighbours are computed from coordinates; a word ladder's neighbours are the dictionary words one letter away; a puzzle state's neighbours are the states one move away. The algorithms are unchanged — BFS needs only a "neighbours of " function and a visited set — but the graph can be astronomically large, so you only ever touch the part you explore. The modelling lesson is about this.
Comparison
| Adjacency List | Adjacency Matrix | |
|---|---|---|
| Space | ||
| Edge lookup | ||
| Iterate neighbors | ||
| Add edge | ||
| Best for | Sparse graphs | Dense graphs, quick edge queries |
The consequence that matters most: BFS and DFS cost on an adjacency list but on a matrix, because finding a vertex's neighbours means scanning its whole row. On a sparse graph with and that is the difference between about and steps. If you need fast edge lookup on a sparse graph, store each vertex's neighbours in a hash set instead of a list: expected lookup at about twice the memory.
Breadth-First Search (BFS)
BFS explores all nodes at distance before exploring nodes at distance . It finds shortest paths in unweighted graphs.
Intuition. Drop a stone in a pond: the ripple reaches everything one unit away, then everything two units away. BFS is that ripple. It keeps a FIFO queue of discovered-but-unprocessed vertices; because a vertex discovered from a distance- vertex is at distance and is appended to the back, the queue always holds a block of distance- vertices followed by a block of distance- vertices. Processing the front therefore processes vertices in order of distance — exactly what a shortest-path search needs when every edge costs the same.
The single most important detail: mark a vertex as discovered when you enqueue it, not when you dequeue it. Marking on dequeue lets the same vertex be enqueued once per incoming edge, which is still correct but can blow the queue up to entries and the running time with it.
graph TD
A["0<br/><small>dist=0</small>"] --> B["1<br/><small>dist=1</small>"]
A --> C["2<br/><small>dist=1</small>"]
B --> D["3<br/><small>dist=2</small>"]
C --> D
D --> E["4<br/><small>dist=3</small>"]
style A fill:#4CAF50,color:#fff
style B fill:#2196F3,color:#fff
style C fill:#2196F3,color:#fff
style D fill:#FF9800,color:#fff
style E fill:#f44336,color:#fff
Trace: BFS from vertex 0
The directed running example 0→1, 0→2, 1→2, 1→3, 2→3, 3→4, started at 0. One row per dequeue; computed by script.
| Step | Dequeue | dist of it | Neighbours scanned | Newly discovered | Queue after |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1, 2 | 1 (d=1), 2 (d=1) | [1, 2] |
| 2 | 1 | 1 | 2, 3 | 3 (d=2) | [2, 3] |
| 3 | 2 | 1 | 3 | — (3 already discovered) | [3] |
| 4 | 3 | 2 | 4 | 4 (d=3) | [4] |
| 5 | 4 | 3 | — | — | [] |
Final distances {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}, matching the diagram. Step 3 is the one to notice: vertex 3 is reachable from 2 as well, but it was already discovered (from 1) at distance 2, and the second route is not shorter, so nothing happens. Recording the vertex each one was discovered from gives the BFS tree: parent(1) = 0, parent(2) = 0, parent(3) = 1, parent(4) = 3, so the shortest path to 4 is 0 → 1 → 3 → 4.
TypeScript:
function bfs(graph: AdjList, start: number): Map<number, number> {
const distances = new Map<number, number>();
const queue: number[] = [start];
distances.set(start, 0);
while (queue.length > 0) {
const node = queue.shift()!;
const dist = distances.get(node)!;
for (const neighbor of graph.get(node) || []) {
if (!distances.has(neighbor)) {
distances.set(neighbor, dist + 1);
queue.push(neighbor);
}
}
}
return distances;
}
Python:
from collections import deque
def bfs(graph: dict[int, list[int]], start: int) -> dict[int, int]:
distances = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor not in distances:
distances[neighbor] = distances[node] + 1
queue.append(neighbor)
return distances
Correction: `queue.shift()` is not O(1)
The TypeScript bfs above uses Array.prototype.shift(), which V8 implements by moving the remaining elements, so it is per call in general. On a graph whose queue grows large (a star, a wide grid) that makes this BFS quadratic rather than . The fix used in the four-language version below is to keep a head index into the array and never remove anything — the array is the queue's history, and queue[head++] is the dequeue.
The canonical version in four languages, with parent pointers for path reconstruction. The tests use the running example plus an isolated vertex 5, and the undirected graph from Try-It Problem 1.
from collections import deque
def bfs(graph: dict[int, list[int]], start: int) -> dict[int, int]:
distances = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor not in distances:
distances[neighbor] = distances[node] + 1
queue.append(neighbor)
return distances
def bfs_path(graph: dict[int, list[int]], start: int, target: int) -> list[int]:
"""A shortest start->target path (fewest edges), or [] if unreachable."""
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == target:
break
for neighbor in graph.get(node, []):
if neighbor not in parent:
parent[neighbor] = node
queue.append(neighbor)
if target not in parent:
return []
path, v = [], target
while v is not None:
path.append(v)
v = parent[v]
return path[::-1]
G = {0: [1, 2], 1: [2, 3], 2: [3], 3: [4], 4: [], 5: []}
assert bfs(G, 0) == {0: 0, 1: 1, 2: 1, 3: 2, 4: 3} # 5 unreachable: absent
assert bfs(G, 3) == {3: 0, 4: 1}
assert bfs_path(G, 0, 4) == [0, 1, 3, 4]
assert bfs_path(G, 0, 5) == []
U = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]} # Try-It Problem 1
assert bfs(U, 0)[3] == 2
print("ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Bfs {
static List<List<Integer>> build(int n, int[][] edges, boolean directed) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) {
g.get(e[0]).add(e[1]);
if (!directed) g.get(e[1]).add(e[0]);
}
return g;
}
/** dist[v] = fewest edges from start to v, or -1 if unreachable; fills parent. */
static int[] bfs(List<List<Integer>> g, int start, int[] parent) {
int[] dist = new int[g.size()];
Arrays.fill(dist, -1);
Arrays.fill(parent, -1);
ArrayDeque<Integer> queue = new ArrayDeque<>();
dist[start] = 0;
queue.add(start);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : g.get(u)) {
if (dist[v] == -1) { // mark on enqueue
dist[v] = dist[u] + 1;
parent[v] = u;
queue.add(v);
}
}
}
return dist;
}
static List<Integer> path(int[] dist, int[] parent, int target) {
LinkedList<Integer> p = new LinkedList<>();
if (dist[target] == -1) return p;
for (int v = target; v != -1; v = parent[v]) p.addFirst(v);
return p;
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {3, 4}};
List<List<Integer>> g = build(6, edges, true); // vertex 5 isolated
int[] parent = new int[6];
int[] dist = bfs(g, 0, parent);
check(Arrays.equals(dist, new int[] {0, 1, 1, 2, 3, -1}));
check(path(dist, parent, 4).equals(List.of(0, 1, 3, 4)));
check(path(dist, parent, 5).isEmpty());
check(Arrays.equals(bfs(g, 3, parent), new int[] {-1, -1, -1, 0, 1, -1}));
List<List<Integer>> u = build(4, new int[][] {{0, 1}, {0, 2}, {1, 2}, {2, 3}}, false);
check(bfs(u, 0, new int[4])[3] == 2); // Try-It Problem 1
System.out.println("ok");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using Graph = std::vector<std::vector<int>>;
Graph build(int n, const std::vector<std::pair<int, int>>& edges, bool directed) {
Graph g(n);
for (auto [u, v] : edges) {
g[u].push_back(v);
if (!directed) g[v].push_back(u);
}
return g;
}
// dist[v] = fewest edges from start to v, or -1 if unreachable; fills parent.
std::vector<int> bfs(const Graph& g, int start, std::vector<int>& parent) {
std::vector<int> dist(g.size(), -1);
parent.assign(g.size(), -1);
std::queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[v] == -1) { // mark on enqueue
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
}
}
return dist;
}
std::vector<int> path(const std::vector<int>& dist, const std::vector<int>& parent, int target) {
std::vector<int> p;
if (dist[target] == -1) return p;
for (int v = target; v != -1; v = parent[v]) p.push_back(v);
std::reverse(p.begin(), p.end());
return p;
}
int main() {
Graph g = build(6, {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {3, 4}}, true); // 5 isolated
std::vector<int> parent;
auto dist = bfs(g, 0, parent);
assert((dist == std::vector<int>{0, 1, 1, 2, 3, -1}));
assert((path(dist, parent, 4) == std::vector<int>{0, 1, 3, 4}));
assert(path(dist, parent, 5).empty());
assert((bfs(g, 3, parent) == std::vector<int>{-1, -1, -1, 0, 1, -1}));
Graph u = build(4, {{0, 1}, {0, 2}, {1, 2}, {2, 3}}, false);
assert(bfs(u, 0, parent)[3] == 2); // Try-It Problem 1
std::cout << "ok\n";
}
type AdjList = Map<number, number[]>;
function bfs(graph: AdjList, start: number): Map<number, number> {
const distances = new Map<number, number>();
const queue: number[] = [start];
distances.set(start, 0);
while (queue.length > 0) {
const node = queue.shift()!;
const dist = distances.get(node)!;
for (const neighbor of graph.get(node) || []) {
if (!distances.has(neighbor)) {
distances.set(neighbor, dist + 1);
queue.push(neighbor);
}
}
}
return distances;
}
// O(V + E) version: a head index instead of shift(), plus parent pointers.
function bfsPath(graph: AdjList, start: number, target: number): number[] {
const parent = new Map<number, number>([[start, -1]]);
const queue: number[] = [start];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
if (node === target) break;
for (const neighbor of graph.get(node) ?? []) {
if (!parent.has(neighbor)) {
parent.set(neighbor, node);
queue.push(neighbor);
}
}
}
if (!parent.has(target)) return [];
const path: number[] = [];
for (let v = target; v !== -1; v = parent.get(v)!) path.push(v);
return path.reverse();
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
const G: AdjList = new Map([[0, [1, 2]], [1, [2, 3]], [2, [3]], [3, [4]], [4, []], [5, []]]);
if (!same([...bfs(G, 0)].sort((a, b) => a[0] - b[0]), [[0, 0], [1, 1], [2, 1], [3, 2], [4, 3]])) throw new Error("dist");
if (!same([...bfs(G, 3)], [[3, 0], [4, 1]])) throw new Error("dist from 3");
if (!same(bfsPath(G, 0, 4), [0, 1, 3, 4])) throw new Error("path");
if (bfsPath(G, 0, 5).length !== 0) throw new Error("unreachable");
const U: AdjList = new Map([[0, [1, 2]], [1, [0, 2]], [2, [0, 1, 3]], [3, [2]]]);
if (bfs(U, 0).get(3) !== 2) throw new Error("Try-It Problem 1");
console.log("ok");
Complexity: time, space.
Why BFS finds shortest paths
Let be the true fewest-edges distance from the start . Claim: BFS sets dist[v] for every reachable , and the queue's labels are always non-decreasing from front to back and differ by at most 1.
Queue invariant. Initially the queue is [s] with label 0. Suppose the queue reads (possibly with no block). Dequeuing the front removes a ; every vertex it discovers is appended with label at the back. The queue still has the form "some s then some s" — or, once the block empties, "some s then some s". So labels leave the queue in non-decreasing order.
Labels are exact. dist[v] is always the length of an actual path (the parent chain), so dist[v] . For the other direction, induct on . For , . For , take a shortest path and let be the vertex before , so and by induction dist[u] . When is dequeued, either is undiscovered and gets label , or was discovered earlier — by some vertex dequeued no later than , whose label is therefore at most , so dist[v] . Either way dist[v] .
Each vertex is enqueued at most once (marked on enqueue) and each adjacency list is scanned once, when its owner is dequeued, which is the bound. With an adjacency matrix the scan of each row is and BFS becomes .
BFS Applications
- Shortest path in unweighted graph
- Level-order traversal of trees
- Connected components (run BFS from each unvisited node)
- Bipartite check (two-color the graph)
- Multi-source BFS (e.g., "rotten oranges" — start from multiple sources simultaneously)
Multi-source BFS is plain BFS with every source enqueued at distance 0 before the loop starts. It computes, for every vertex, the distance to the nearest source in one pass — the same as adding a virtual super-source with a 0-length edge to each real source. Running a separate BFS from each of sources would cost times as much. The BFS lesson adds 0-1 BFS, bidirectional BFS and BFS on grids with state.
Bipartite Check
Python:
def is_bipartite(graph: dict[int, list[int]], n: int) -> bool:
color = [-1] * n
for start in range(n):
if color[start] != -1:
continue
queue = deque([start])
color[start] = 0
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if color[neighbor] == -1:
color[neighbor] = 1 - color[node]
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False
return True
Self-checking, with the missing import added (the block above uses deque without importing it):
from collections import deque
def is_bipartite(graph: dict[int, list[int]], n: int) -> bool:
color = [-1] * n
for start in range(n):
if color[start] != -1:
continue
queue = deque([start])
color[start] = 0
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if color[neighbor] == -1:
color[neighbor] = 1 - color[node]
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False
return True
square = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [2, 0]} # even cycle
triangle = {0: [1, 2], 1: [0, 2], 2: [0, 1]} # odd cycle
two_parts = {0: [1], 1: [0], 2: [3, 4], 3: [2, 4], 4: [2, 3]} # second component is a triangle
assert is_bipartite(square, 4)
assert not is_bipartite(triangle, 3)
assert not is_bipartite(two_parts, 5) # only found because of the outer loop over all starts
print("ok")
Why it is correct. A graph is bipartite if and only if it has no odd cycle. If the BFS colouring succeeds, every edge joins different colours, so the colours are the two sides. If it fails, it found an edge with equal colours; in BFS from a root , colour equals depth parity, so the tree paths and have equal parity, and together with the edge they contain a cycle of odd length — which no bipartite graph can have, because a cycle must alternate sides and therefore have even length. The outer loop over every start vertex is essential: two_parts above is bipartite in its first component and not in its second.
Depth-First Search (DFS)
DFS explores as deep as possible before backtracking. It is the foundation of many graph algorithms.
Intuition. DFS is how you explore a maze with a ball of string: keep walking into unexplored corridors; at a dead end, wind the string back to the last junction with an unexplored corridor. The string is the recursion stack. Where BFS answers "how far?", DFS answers structural questions — "is there a cycle?", "what must come before what?", "which vertices are mutually reachable?" — because the moment DFS finishes a vertex (returns from its call), it has explored everything reachable from it. That finish order is the secret ingredient of topological sort, Kosaraju's SCC algorithm and the low-link algorithms in the connectivity lesson.
Record a counter time that ticks on entering and leaving each vertex, and every vertex gets a discovery time and a finish time . The parenthesis theorem (CLRS 3rd edition, Theorem 22.7) says the intervals of any two vertices are either disjoint or nested, never partially overlapping — nested exactly when one is a descendant of the other in the DFS forest. The white-path theorem says becomes a descendant of if and only if, at time , there is a path from to through vertices not yet discovered.
These give the four edge types of a directed DFS. For an edge examined while is on the stack:
| Edge type | Colour of when examined | Meaning |
|---|---|---|
| Tree | white (undiscovered) | DFS descends along it |
| Back | gray (on the stack) | is an ancestor of : a cycle |
| Forward | black, and | is an already-finished descendant |
| Cross | black, and | is in a finished, unrelated subtree |
In an undirected graph only tree and back edges occur (every non-tree edge connects a vertex to an ancestor), which is why undirected cycle detection only has to skip the edge back to the parent.
flowchart LR
A["0 (d=1, f=10)"] -->|"tree"| B["1 (d=2, f=9)"]
B -->|"tree"| C["2 (d=3, f=8)"]
C -->|"tree"| D["3 (d=4, f=7)"]
D -->|"tree"| E["4 (d=5, f=6)"]
B -.->|"forward"| D
A -.->|"forward"| C
Trace: recursive DFS from vertex 0
The same directed running example. Neighbours are visited in list order. Computed by script.
| Event | Vertex | time | Stack (call chain) after | Edge examined → type |
|---|---|---|---|---|
| enter | 0 | 1 | 0 | 0→1 tree |
| enter | 1 | 2 | 0, 1 | 1→2 tree |
| enter | 2 | 3 | 0, 1, 2 | 2→3 tree |
| enter | 3 | 4 | 0, 1, 2, 3 | 3→4 tree |
| enter | 4 | 5 | 0, 1, 2, 3, 4 | (no out-edges) |
| finish | 4 | 6 | 0, 1, 2, 3 | — |
| finish | 3 | 7 | 0, 1, 2 | — |
| finish | 2 | 8 | 0, 1 | then 1→3: 3 is black, → forward |
| finish | 1 | 9 | 0 | then 0→2: 2 is black, → forward |
| finish | 0 | 10 | — | — |
Discovery/finish times: 0 = (1, 10), 1 = (2, 9), 2 = (3, 8), 3 = (4, 7), 4 = (5, 6). The intervals are perfectly nested because the DFS tree here is a single path. No back edge, so the graph is acyclic; the reverse finish order 0, 1, 2, 3, 4 is a topological order.
TypeScript:
function dfs(graph: AdjList, start: number): Set<number> {
const visited = new Set<number>();
function explore(node: number): void {
visited.add(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
explore(neighbor);
}
}
}
explore(start);
return visited;
}
// Iterative DFS
function dfsIterative(graph: AdjList, start: number): Set<number> {
const visited = new Set<number>();
const stack = [start];
while (stack.length > 0) {
const node = stack.pop()!;
if (visited.has(node)) continue;
visited.add(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
return visited;
}
Python:
def dfs(graph: dict[int, list[int]], start: int) -> set[int]:
visited = set()
def explore(node: int) -> None:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
explore(neighbor)
explore(start)
return visited
def dfs_iterative(graph: dict[int, list[int]], start: int) -> set[int]:
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
stack.append(neighbor)
return visited
Trace: the iterative version visits in a different order
The iterative DFS above pushes all unvisited neighbours and pops the last one, so it explores neighbours in reverse list order, and it can push the same vertex more than once. On the running example, computed by script:
| Pop # | Popped | Visited order so far | Stack after |
|---|---|---|---|
| 1 | 0 | 0 | [1, 2] |
| 2 | 2 | 0, 2 | [1, 3] |
| 3 | 3 | 0, 2, 3 | [1, 4] |
| 4 | 4 | 0, 2, 3, 4 | [1] |
| 5 | 1 | 0, 2, 3, 4, 1 | [] |
Both versions reach the same set , so for reachability they are interchangeable. But the visit order differs (0, 1, 2, 3, 4 recursively versus 0, 2, 3, 4, 1 here), and more importantly this version has no notion of "finishing" a vertex, so it cannot be used as-is for topological sort, three-colour cycle detection or low-links. For those, the iterative form must simulate the call stack: push (vertex, next-neighbour-index) frames and record the finish time when a frame's neighbours are exhausted. The C++ and Java versions below include that, and the DFS lesson develops it fully.
Correction: iterative DFS space
The page states space for DFS. That is right for the recursive version (the stack holds at most one frame per vertex), but the iterative version above pushes a vertex once per incoming edge examined before it is visited, so its stack can hold up to entries. On a complete graph that is . The frame-based iterative DFS below is back to .
The four-language version. Tests: reachable sets from 0 and from 3, the recursive and iterative visit orders traced above, and a 100,000-vertex path that the iterative version handles but the recursive one would not (Python's default recursion limit is 1,000; the JVM's default thread stack typically overflows somewhere in the low tens of thousands of frames).
def dfs(graph: dict[int, list[int]], start: int) -> set[int]:
visited = set()
def explore(node: int) -> None:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
explore(neighbor)
explore(start)
return visited
def dfs_iterative(graph: dict[int, list[int]], start: int) -> set[int]:
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
stack.append(neighbor)
return visited
def dfs_order(graph: dict[int, list[int]], start: int) -> list[int]:
"""Recursive preorder (visit order)."""
order: list[int] = []
seen: set[int] = set()
def explore(u: int) -> None:
seen.add(u)
order.append(u)
for v in graph.get(u, []):
if v not in seen:
explore(v)
explore(start)
return order
def dfs_iterative_order(graph: dict[int, list[int]], start: int) -> list[int]:
order: list[int] = []
seen: set[int] = set()
stack = [start]
while stack:
u = stack.pop()
if u in seen:
continue
seen.add(u)
order.append(u)
stack.extend(v for v in graph.get(u, []) if v not in seen)
return order
G = {0: [1, 2], 1: [2, 3], 2: [3], 3: [4], 4: []}
assert dfs(G, 0) == dfs_iterative(G, 0) == {0, 1, 2, 3, 4}
assert dfs(G, 3) == {3, 4}
assert dfs_order(G, 0) == [0, 1, 2, 3, 4]
assert dfs_iterative_order(G, 0) == [0, 2, 3, 4, 1]
chain = {i: [i + 1] for i in range(99_999)}
assert len(dfs_iterative(chain, 0)) == 100_000
try:
dfs(chain, 0)
raise AssertionError("expected RecursionError")
except RecursionError:
pass # recursive DFS cannot handle a 100,000-deep path with default limits
print("ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
public class Dfs {
static List<List<Integer>> build(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) g.get(e[0]).add(e[1]);
return g;
}
static void explore(List<List<Integer>> g, int u, boolean[] seen, List<Integer> order) {
seen[u] = true;
order.add(u);
for (int v : g.get(u)) if (!seen[v]) explore(g, v, seen, order);
}
static List<Integer> dfsRecursive(List<List<Integer>> g, int start) {
List<Integer> order = new ArrayList<>();
explore(g, start, new boolean[g.size()], order);
return order;
}
/** Push-all-neighbours iterative DFS: reverse neighbour order, O(E) stack. */
static List<Integer> dfsIterative(List<List<Integer>> g, int start) {
boolean[] seen = new boolean[g.size()];
List<Integer> order = new ArrayList<>();
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int u = stack.pop();
if (seen[u]) continue;
seen[u] = true;
order.add(u);
for (int v : g.get(u)) if (!seen[v]) stack.push(v);
}
return order;
}
/** Frame-based iterative DFS: same order as recursion, O(V) stack, gives finish order. */
static List<Integer> finishOrder(List<List<Integer>> g, int start) {
int n = g.size();
boolean[] seen = new boolean[n];
int[] next = new int[n]; // next neighbour index per vertex
List<Integer> finished = new ArrayList<>();
ArrayDeque<Integer> stack = new ArrayDeque<>();
seen[start] = true;
stack.push(start);
while (!stack.isEmpty()) {
int u = stack.peek();
if (next[u] < g.get(u).size()) {
int v = g.get(u).get(next[u]++);
if (!seen[v]) { seen[v] = true; stack.push(v); }
} else {
finished.add(stack.pop());
}
}
return finished;
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
List<List<Integer>> g = build(5, new int[][] {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {3, 4}});
check(dfsRecursive(g, 0).equals(List.of(0, 1, 2, 3, 4)));
check(dfsIterative(g, 0).equals(List.of(0, 2, 3, 4, 1)));
check(dfsRecursive(g, 3).equals(List.of(3, 4)));
check(finishOrder(g, 0).equals(List.of(4, 3, 2, 1, 0)));
int n = 100_000;
int[][] chainEdges = new int[n - 1][];
for (int i = 0; i + 1 < n; i++) chainEdges[i] = new int[] {i, i + 1};
List<List<Integer>> chain = build(n, chainEdges);
check(dfsIterative(chain, 0).size() == n);
check(finishOrder(chain, 0).get(0) == n - 1);
System.out.println("ok");
}
}
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
using Graph = std::vector<std::vector<int>>;
Graph build(int n, const std::vector<std::pair<int, int>>& edges) {
Graph g(n);
for (auto [u, v] : edges) g[u].push_back(v);
return g;
}
void explore(const Graph& g, int u, std::vector<bool>& seen, std::vector<int>& order) {
seen[u] = true;
order.push_back(u);
for (int v : g[u])
if (!seen[v]) explore(g, v, seen, order);
}
std::vector<int> dfsRecursive(const Graph& g, int start) {
std::vector<bool> seen(g.size(), false);
std::vector<int> order;
explore(g, start, seen, order);
return order;
}
// Push-all-neighbours iterative DFS: reverse neighbour order, O(E) stack.
std::vector<int> dfsIterative(const Graph& g, int start) {
std::vector<bool> seen(g.size(), false);
std::vector<int> order, stack{start};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
if (seen[u]) continue;
seen[u] = true;
order.push_back(u);
for (int v : g[u])
if (!seen[v]) stack.push_back(v);
}
return order;
}
// Frame-based iterative DFS: recursion order, O(V) stack, returns finish order.
std::vector<int> finishOrder(const Graph& g, int start) {
std::vector<bool> seen(g.size(), false);
std::vector<std::size_t> next(g.size(), 0);
std::vector<int> finished, stack{start};
seen[start] = true;
while (!stack.empty()) {
int u = stack.back();
if (next[u] < g[u].size()) {
int v = g[u][next[u]++];
if (!seen[v]) { seen[v] = true; stack.push_back(v); }
} else {
finished.push_back(u);
stack.pop_back();
}
}
return finished;
}
int main() {
Graph g = build(5, {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {3, 4}});
assert((dfsRecursive(g, 0) == std::vector<int>{0, 1, 2, 3, 4}));
assert((dfsIterative(g, 0) == std::vector<int>{0, 2, 3, 4, 1}));
assert((dfsRecursive(g, 3) == std::vector<int>{3, 4}));
assert((finishOrder(g, 0) == std::vector<int>{4, 3, 2, 1, 0}));
const int n = 100000;
std::vector<std::pair<int, int>> chainEdges;
for (int i = 0; i + 1 < n; i++) chainEdges.push_back({i, i + 1});
Graph chain = build(n, chainEdges);
assert(dfsIterative(chain, 0).size() == static_cast<std::size_t>(n));
assert(finishOrder(chain, 0).front() == n - 1);
std::cout << "ok\n";
}
type AdjList = Map<number, number[]>;
function dfs(graph: AdjList, start: number): Set<number> {
const visited = new Set<number>();
function explore(node: number): void {
visited.add(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
explore(neighbor);
}
}
}
explore(start);
return visited;
}
// Iterative DFS
function dfsIterative(graph: AdjList, start: number): Set<number> {
const visited = new Set<number>();
const stack = [start];
while (stack.length > 0) {
const node = stack.pop()!;
if (visited.has(node)) continue;
visited.add(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
return visited;
}
// A Set iterates in insertion order, so [...set] is the visit order.
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
const G: AdjList = new Map([[0, [1, 2]], [1, [2, 3]], [2, [3]], [3, [4]], [4, []]]);
if (!same([...dfs(G, 0)], [0, 1, 2, 3, 4])) throw new Error("recursive order");
if (!same([...dfsIterative(G, 0)], [0, 2, 3, 4, 1])) throw new Error("iterative order");
if (!same([...dfs(G, 3)], [3, 4])) throw new Error("reach from 3");
const chain: AdjList = new Map();
for (let i = 0; i < 99_999; i++) chain.set(i, [i + 1]);
if (dfsIterative(chain, 0).size !== 100_000) throw new Error("deep chain");
console.log("ok");
Complexity: time, space.
The time bound has the same argument as BFS: each vertex is entered once (guarded by visited) and each adjacency list is scanned once, during its owner's call. Space is the visited set plus the stack: for recursion or frames, for the push-all iterative form.
DFS Applications
- Cycle detection (back edges in directed graphs)
- Topological sort (ordering dependencies)
- Connected components / flood fill
- Path finding (does a path exist?)
- Strongly connected components (Tarjan's, Kosaraju's)
DFS does not find shortest paths. The first time DFS reaches a vertex it may have taken a long detour: on the running example, DFS reaches 3 via 0 → 1 → 2 → 3 (three edges) although 0 → 1 → 3 has two. Use BFS for fewest edges.
Cycle Detection in Directed Graph
Python:
def has_cycle_directed(graph: dict[int, list[int]], n: int) -> bool:
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(node: int) -> bool:
color[node] = GRAY # currently in the call stack
for neighbor in graph.get(node, []):
if color[neighbor] == GRAY: # back edge → cycle
return True
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK # fully processed
return False
return any(color[i] == WHITE and dfs(i) for i in range(n))
TIP
The three-color technique (WHITE/GRAY/BLACK) distinguishes between unvisited nodes, nodes currently in the recursion stack, and fully processed nodes. A back edge (pointing to a GRAY node) indicates a cycle.
Self-checking version on Try-It Problem 2, the running example, a self-loop, and the classic false positive for two colours:
def has_cycle_directed(graph: dict[int, list[int]], n: int) -> bool:
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(node: int) -> bool:
color[node] = GRAY # currently in the call stack
for neighbor in graph.get(node, []):
if color[neighbor] == GRAY: # back edge → cycle
return True
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK # fully processed
return False
return any(color[i] == WHITE and dfs(i) for i in range(n))
assert has_cycle_directed({0: [1], 1: [2], 2: [0]}, 3) # Try-It Problem 2
assert not has_cycle_directed({0: [1, 2], 1: [2, 3], 2: [3], 3: [4]}, 5) # running example
assert has_cycle_directed({0: [0]}, 1) # self-loop
# Diamond 0->1->3, 0->2->3: vertex 3 is reached twice but there is no cycle.
# A "visited = cycle" test (two colours) would wrongly report one here.
assert not has_cycle_directed({0: [1, 2], 1: [3], 2: [3]}, 4)
print("ok")
Proof that a back edge exists if and only if there is a cycle. If DFS finds an edge with gray, then is on the current call stack, so there is a tree path , and with the edge it closes a cycle. Conversely, suppose there is a cycle and let be its first vertex discovered by DFS, with its predecessor on the cycle. At time the rest of the cycle is white, so by the white-path theorem becomes a descendant of ; when DFS examines , is still gray (it finishes only after all its descendants), so the edge is a back edge.
The "gray versus black" distinction is the whole point: a black vertex was reached before by some other route, which in a directed graph is perfectly legal (the diamond in the test). In an undirected graph you need only two states plus the parent: any visited neighbour other than the vertex you came from closes a cycle. Union-Find is the other standard undirected cycle detector.
Shortest Path Algorithms
Every algorithm in this section is built from one operation. Relaxing an edge of weight means: if going through beats the best known route to , take it.
dist[v] is always the length of some real path (or infinity), so it only ever decreases toward the true distance . The algorithms differ only in which edges they relax in which order: Dijkstra relaxes the out-edges of the closest unfinished vertex, Bellman-Ford relaxes every edge in rounds, a DAG algorithm relaxes in topological order, and Floyd-Warshall relaxes through one intermediate vertex at a time. Each order is correct under different assumptions about the weights — that is the whole comparison table at the end of this section.
Dijkstra's Algorithm
Finds shortest paths from a source to all vertices in a graph with non-negative edge weights.
Intuition. Grow a "settled" region outward from the source, always settling the unsettled vertex with the smallest tentative distance. With non-negative weights that vertex cannot be improved later: any other route to it leaves the settled region through some vertex that is already at least as far away, and edges cannot make a route shorter. It is BFS's ripple with uneven edge lengths, and the priority queue replaces the FIFO queue.
graph LR
A["A"] -->|4| B["B"]
A -->|1| C["C"]
B -->|1| D["D"]
C -->|5| D
C -->|2| B
Trace: Dijkstra from A
The graph above, with the binary-heap "lazy deletion" implementation below (push a new entry on every improvement; skip stale entries on pop). One row per heap pop; computed by script. Ties in the heap break by vertex name.
| Pop | Entry popped | Action | dist after | Heap after |
|---|---|---|---|---|
| 1 | (0, A) | relax A→B: B = 4; A→C: C = 1 | A 0, B 4, C 1 | (1, C), (4, B) |
| 2 | (1, C) | relax C→D: D = 6; C→B: 1 + 2 = 3 < 4, B = 3 | A 0, B 3, C 1, D 6 | (3, B), (4, B), (6, D) |
| 3 | (3, B) | relax B→D: 3 + 1 = 4 < 6, D = 4 | A 0, B 3, C 1, D 4 | (4, B), (4, D), (6, D) |
| 4 | (4, B) | stale: 4 > dist[B] = 3, skip | unchanged | (4, D), (6, D) |
| 5 | (4, D) | D has no out-edges | A 0, B 3, C 1, D 4 | (6, D) |
| 6 | (6, D) | stale: 6 > dist[D] = 4, skip | unchanged | empty |
Six pushes, four real pops, two stale pops. Shortest A→D is 4 along A → C → B → D (parents: D ← B ← C ← A). Notice B was first reached directly at cost 4 and later improved to 3 through C; that is why B cannot be settled when it is first seen.
TypeScript:
function dijkstra(
graph: Map<number, [number, number][]>,
start: number
): Map<number, number> {
const dist = new Map<number, number>();
dist.set(start, 0);
// MinHeap: [distance, node]
// Using a simple sorted insertion for clarity
// In production, use a proper priority queue
const pq: [number, number][] = [[0, start]];
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift()!;
if (d > (dist.get(u) ?? Infinity)) continue;
for (const [v, weight] of graph.get(u) || []) {
const newDist = d + weight;
if (newDist < (dist.get(v) ?? Infinity)) {
dist.set(v, newDist);
pq.push([newDist, v]);
}
}
}
return dist;
}
Python:
import heapq
def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, float]:
dist: dict[int, float] = {start: 0}
pq = [(0, start)] # (distance, node)
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float('inf')):
continue
for v, weight in graph.get(u, []):
new_dist = d + weight
if new_dist < dist.get(v, float('inf')):
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
Complexity: with a binary heap. with a simple array (better for dense graphs).
DANGER
Dijkstra fails with negative edge weights. A negative edge can create a shorter path through a node that was already finalized. Use Bellman-Ford instead.
Correction (precision): what "fails" means for these two implementations
The statement is exactly right for textbook Dijkstra, which marks a vertex final when it is popped and never reconsiders it: with a negative edge it can return a wrong distance. The lazy-deletion code on this page is subtly different — it never marks anything final; it re-pushes any vertex whose distance improves. With negative edges but no negative cycle it still terminates with correct distances, but a vertex can be re-processed many times and the worst case is exponential in (and with a negative cycle it never terminates). So the practical rule stands: never run Dijkstra with negative weights. Use Bellman-Ford, or Johnson's reweighting from the shortest-paths lesson when you need many sources.
The TypeScript version also sorts the whole array on every iteration and uses shift(), which costs per pop for a queue of size — fine for the five-vertex example, hopeless at vertices. The four-language version below uses a real binary heap.
The canonical version in four languages with parent pointers. Tests: the trace graph with A, B, C, D numbered 0–3 and an unreachable vertex 4.
import heapq
def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, float]:
dist: dict[int, float] = {start: 0}
pq = [(0, start)] # (distance, node)
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float('inf')):
continue
for v, weight in graph.get(u, []):
new_dist = d + weight
if new_dist < dist.get(v, float('inf')):
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
def dijkstra_path(graph: dict[int, list[tuple[int, int]]], start: int, target: int) -> tuple[float, list[int]]:
dist: dict[int, float] = {start: 0}
parent: dict[int, int] = {}
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
if u == target: # settled: its distance is final
break
for v, w in graph.get(u, []):
if d + w < dist.get(v, float("inf")):
dist[v] = d + w
parent[v] = u
heapq.heappush(pq, (d + w, v))
if target not in dist:
return float("inf"), []
path = [target]
while path[-1] != start:
path.append(parent[path[-1]])
return dist[target], path[::-1]
# A=0, B=1, C=2, D=3; vertex 4 is unreachable.
W = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(3, 5), (1, 2)], 3: [], 4: []}
assert dijkstra(W, 0) == {0: 0, 1: 3, 2: 1, 3: 4}
assert dijkstra_path(W, 0, 3) == (4, [0, 2, 1, 3])
assert dijkstra_path(W, 0, 4) == (float("inf"), [])
print("ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
public class Dijkstra {
static final long INF = Long.MAX_VALUE;
/** g.get(u) holds {v, w} pairs. Returns dist (INF if unreachable) and fills parent. */
static long[] dijkstra(List<List<int[]>> g, int src, int[] parent) {
int n = g.size();
long[] dist = new long[n];
Arrays.fill(dist, INF);
Arrays.fill(parent, -1);
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
dist[src] = 0;
pq.add(new long[] {0, src});
while (!pq.isEmpty()) {
long[] top = pq.poll();
long d = top[0];
int u = (int) top[1];
if (d > dist[u]) continue; // stale entry
for (int[] e : g.get(u)) {
int v = e[0];
long nd = d + e[1];
if (nd < dist[v]) {
dist[v] = nd;
parent[v] = u;
pq.add(new long[] {nd, v});
}
}
}
return dist;
}
static List<Integer> path(long[] dist, int[] parent, int target) {
LinkedList<Integer> p = new LinkedList<>();
if (dist[target] == INF) return p;
for (int v = target; v != -1; v = parent[v]) p.addFirst(v);
return p;
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
int n = 5; // A=0, B=1, C=2, D=3; 4 unreachable
int[][] edges = {{0, 1, 4}, {0, 2, 1}, {1, 3, 1}, {2, 3, 5}, {2, 1, 2}};
List<List<int[]>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) g.get(e[0]).add(new int[] {e[1], e[2]});
int[] parent = new int[n];
long[] dist = dijkstra(g, 0, parent);
check(Arrays.equals(dist, new long[] {0, 3, 1, 4, INF}));
check(path(dist, parent, 3).equals(List.of(0, 2, 1, 3)));
check(path(dist, parent, 4).isEmpty());
System.out.println("ok");
}
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using WGraph = std::vector<std::vector<std::pair<int, int>>>; // (neighbor, weight)
constexpr long long INF = std::numeric_limits<long long>::max();
std::vector<long long> dijkstra(const WGraph& g, int src, std::vector<int>& parent) {
std::vector<long long> dist(g.size(), INF);
parent.assign(g.size(), -1);
using Item = std::pair<long long, int>; // (distance, vertex)
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : g[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
return dist;
}
std::vector<int> path(const std::vector<long long>& dist, const std::vector<int>& parent, int target) {
std::vector<int> p;
if (dist[target] == INF) return p;
for (int v = target; v != -1; v = parent[v]) p.push_back(v);
std::reverse(p.begin(), p.end());
return p;
}
int main() {
WGraph g(5); // A=0, B=1, C=2, D=3; 4 unreachable
for (auto [u, v, w] : std::vector<std::tuple<int, int, int>>{{0, 1, 4}, {0, 2, 1}, {1, 3, 1}, {2, 3, 5}, {2, 1, 2}})
g[u].push_back({v, w});
std::vector<int> parent;
auto dist = dijkstra(g, 0, parent);
assert((dist == std::vector<long long>{0, 3, 1, 4, INF}));
assert((path(dist, parent, 3) == std::vector<int>{0, 2, 1, 3}));
assert(path(dist, parent, 4).empty());
std::cout << "ok\n";
}
function dijkstra(
graph: Map<number, [number, number][]>,
start: number
): Map<number, number> {
const dist = new Map<number, number>();
dist.set(start, 0);
// MinHeap: [distance, node]
// Using a simple sorted insertion for clarity
// In production, use a proper priority queue
const pq: [number, number][] = [[0, start]];
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift()!;
if (d > (dist.get(u) ?? Infinity)) continue;
for (const [v, weight] of graph.get(u) || []) {
const newDist = d + weight;
if (newDist < (dist.get(v) ?? Infinity)) {
dist.set(v, newDist);
pq.push([newDist, v]);
}
}
}
return dist;
}
// A proper binary min-heap of [distance, vertex] pairs.
class MinHeap {
items: [number, number][] = [];
get size(): number { return this.items.length; }
push(x: [number, number]): void {
const a = this.items;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p][0] <= a[i][0]) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop(): [number, number] {
const a = this.items;
const top = a[0];
const last = a.pop()!;
if (a.length > 0) {
a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && a[l][0] < a[m][0]) m = l;
if (r < a.length && a[r][0] < a[m][0]) m = r;
if (m === i) break;
[a[m], a[i]] = [a[i], a[m]];
i = m;
}
}
return top;
}
}
function dijkstraHeap(graph: Map<number, [number, number][]>, start: number): { dist: Map<number, number>; parent: Map<number, number> } {
const dist = new Map<number, number>([[start, 0]]);
const parent = new Map<number, number>();
const pq = new MinHeap();
pq.push([0, start]);
while (pq.size > 0) {
const [d, u] = pq.pop();
if (d > dist.get(u)!) continue;
for (const [v, w] of graph.get(u) ?? []) {
if (d + w < (dist.get(v) ?? Infinity)) {
dist.set(v, d + w);
parent.set(v, u);
pq.push([d + w, v]);
}
}
}
return { dist, parent };
}
// A=0, B=1, C=2, D=3; vertex 4 is unreachable.
const W = new Map<number, [number, number][]>([[0, [[1, 4], [2, 1]]], [1, [[3, 1]]], [2, [[3, 5], [1, 2]]], [3, []], [4, []]]);
const expected = [[0, 0], [1, 3], [2, 1], [3, 4]];
const sorted = (m: Map<number, number>) => JSON.stringify([...m].sort((a, b) => a[0] - b[0]));
if (sorted(dijkstra(W, 0)) !== JSON.stringify(expected)) throw new Error("sort-based");
const { dist, parent } = dijkstraHeap(W, 0);
if (sorted(dist) !== JSON.stringify(expected)) throw new Error("heap-based");
const path = [3];
while (path[path.length - 1] !== 0) path.push(parent.get(path[path.length - 1])!);
if (JSON.stringify(path.reverse()) !== JSON.stringify([0, 2, 1, 3])) throw new Error("path");
if (dist.has(4)) throw new Error("unreachable");
console.log("ok");
Why Dijkstra is correct
Invariant: when a vertex is popped with (a non-stale pop), , the true distance.
Proof. Suppose not, and let be the first vertex popped non-stale with . Take a true shortest path , and let be the first vertex on it that has not yet been popped non-stale, with its predecessor ( has been popped; is possible). Because was popped correctly (it came before ), , and when was popped the edge was relaxed, so — that is, already has its correct distance and an entry in the heap with that key. Now the non-negativity of weights does the work: lies on a shortest path to before , so . Hence
The heap holds an entry for with key , so the heap would have popped before — unless , which contradicts . Either way, contradiction.
The step "" is the only place non-negativity is used, and it is exactly what a negative edge breaks: with the vertex after can be closer than .
Complexity. Every edge relaxation pushes at most one heap entry, so the heap holds at most entries; each push and pop costs . Total . With an array instead of a heap (scan for the minimum unsettled vertex), each of the settle steps costs and each relaxation : , which beats the heap when is close to . A Fibonacci heap gives in theory (Fredman and Tarjan, 1987) but is rarely faster in practice than a binary heap because of its constants.
Bellman-Ford Algorithm
Handles graphs with negative edge weights. Detects negative-weight cycles.
Python:
def bellman_ford(n: int, edges: list[tuple[int, int, int]], start: int) -> dict[int, float]:
"""edges: [(u, v, weight), ...]"""
dist: dict[int, float] = {i: float('inf') for i in range(n)}
dist[start] = 0
# Relax all edges V-1 times
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative-weight cycles
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("Graph contains a negative-weight cycle")
return dist
Complexity: time, space.
Trace: Bellman-Ford with a negative edge
Edges in this order: 0→1 (4), 0→2 (5), 1→3 (3), 2→1 (−3), 3→2 (2). The cycle 1 → 3 → 2 → 1 has weight , so shortest paths exist. Distances after each full round, computed by script:
| After round | dist[0] | dist[1] | dist[2] | dist[3] | What changed |
|---|---|---|---|---|---|
| 0 (init) | 0 | ∞ | ∞ | ∞ | — |
| 1 | 0 | 2 | 5 | 7 | 1 = 4, 2 = 5, 3 = 4 + 3 = 7, then 2→1 improves 1 to 5 − 3 = 2 |
| 2 | 0 | 2 | 5 | 5 | 1→3 now gives 2 + 3 = 5 |
| 3 | 0 | 2 | 5 | 5 | nothing: converged |
Dijkstra would settle vertex 1 at distance 4 before discovering that 0 → 2 → 1 costs 2. Bellman-Ford does not care about order; it just keeps relaxing. Round 1 already propagated two edges deep for vertex 1 because of the edge order — the guarantee below is a lower bound on progress, not an exact description.
Why it is correct. Claim: after rounds, is at most the weight of the shortest path from to that uses at most edges. Induction on : the case is the initialisation. If the best path with at most edges ends with edge , its prefix to has at most edges, so after round , is at most the prefix weight, and round relaxes . If there is no negative cycle reachable from , some shortest path to every vertex is simple, hence has at most edges, so rounds suffice — and since dist is always the length of some real walk, it cannot go below . Conversely, if a negative cycle is reachable and no edge on it could still be relaxed, then for all ; summing around the cycle the dist terms cancel and leave , a contradiction. So the final check fires.
Correction: "detects negative-weight cycles" means cycles reachable from the source
The final loop only catches a negative cycle that the source can reach. For an unreachable cycle every vertex on it keeps dist = inf, and inf + w < inf is false, so no error is raised (the test below demonstrates this). That is usually what you want for single-source distances. To detect a negative cycle anywhere, initialise every dist to 0 instead — equivalent to adding a virtual source with a 0-weight edge to every vertex — which is exactly the first step of Johnson's algorithm.
Self-checking, using the trace graph:
def bellman_ford(n: int, edges: list[tuple[int, int, int]], start: int) -> dict[int, float]:
"""edges: [(u, v, weight), ...]"""
dist: dict[int, float] = {i: float('inf') for i in range(n)}
dist[start] = 0
# Relax all edges V-1 times
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative-weight cycles
for u, v, w in edges:
if dist[u] + w < dist[v]:
raise ValueError("Graph contains a negative-weight cycle")
return dist
E = [(0, 1, 4), (0, 2, 5), (1, 3, 3), (2, 1, -3), (3, 2, 2)]
assert bellman_ford(4, E, 0) == {0: 0, 1: 2, 2: 5, 3: 5}
try: # make the cycle 1->3->2->1 negative
bellman_ford(4, [(0, 1, 4), (1, 3, 3), (3, 2, 2), (2, 1, -6)], 0)
raise AssertionError("expected ValueError")
except ValueError:
pass
# An unreachable negative cycle (4 <-> 5) is NOT reported:
d = bellman_ford(6, E + [(4, 5, -1), (5, 4, -1)], 0)
assert d[4] == float("inf") and d[3] == 5
print("ok")
A common speed-up stops as soon as a full round changes nothing (round 3 in the trace). The queue-based variant usually called SPFA only re-relaxes edges out of vertices whose distance just changed; it is often fast on random graphs but still in the worst case, and contest setters build inputs that make it time out.
Floyd-Warshall Algorithm
Finds shortest paths between all pairs of vertices.
Python:
def floyd_warshall(n: int, edges: list[tuple[int, int, int]]) -> list[list[float]]:
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Complexity: time, space.
Why it is correct. Let be the shortest path whose intermediate vertices all lie in . is the edge weights. A shortest path allowed to use vertex either avoids it — weight — or passes through it once (with no negative cycles, a shortest path is simple), splitting into and , each using only inside. So . Updating a single matrix in place is safe because round never changes row or column : could only improve through , and . After all rounds every vertex is allowed as an intermediate. If for some at the end, lies on a negative cycle.
Correction: parallel edges
dist[u][v] = w keeps the last edge between a pair, not the cheapest. If the input lists (0, 1, 2) and then (0, 1, 5), the matrix starts with 5 and the answer for 0 → 1 is wrong. Use dist[u][v] = min(dist[u][v], w) — the version below. (For undirected input, also set dist[v][u].)
def floyd_warshall(n: int, edges: list[tuple[int, int, int]]) -> list[list[float]]:
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
def floyd_warshall_fixed(n: int, edges: list[tuple[int, int, int]]) -> list[list[float]]:
INF = float("inf")
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w) # keep the cheapest parallel edge
for k in range(n):
dk = dist[k]
for i in range(n):
dik = dist[i][k]
if dik == INF:
continue
di = dist[i]
for j in range(n):
if dik + dk[j] < di[j]:
di[j] = dik + dk[j]
return dist
# The Dijkstra example (A..D = 0..3): all-pairs agrees with single-source.
E = [(0, 1, 4), (0, 2, 1), (1, 3, 1), (2, 3, 5), (2, 1, 2)]
assert floyd_warshall(4, E)[0] == [0, 3, 1, 4]
assert floyd_warshall_fixed(4, E)[0] == [0, 3, 1, 4]
assert floyd_warshall_fixed(4, E)[2][3] == 3 # 2 -> 1 -> 3
# Parallel edges: the original keeps the last one (wrong), the fix keeps the min.
assert floyd_warshall(2, [(0, 1, 2), (0, 1, 5)])[0][1] == 5
assert floyd_warshall_fixed(2, [(0, 1, 2), (0, 1, 5)])[0][1] == 2
# Negative cycle shows up on the diagonal.
assert floyd_warshall_fixed(3, [(0, 1, 1), (1, 2, -3), (2, 0, 1)])[0][0] < 0
print("ok")
The triple loop is short enough that its constant is tiny: hoisting dist[k] and dist[i] out of the inner loop (as in the fixed version) and skipping rows with dist[i][k] = inf are the standard micro-optimisations. In C++ with a flat array, ( inner iterations) runs in well under a second; in pure Python, of a couple of hundred is the practical limit.
Algorithm Comparison
| Algorithm | Weights | Negative? | All-pairs? | Complexity |
|---|---|---|---|---|
| BFS | Unweighted | N/A | No | |
| Dijkstra | Non-negative | No | No | |
| Bellman-Ford | Any | Yes (detects cycles) | No | |
| Floyd-Warshall | Any | Yes | Yes | |
| 0-1 BFS | Only 0 and 1 | No | No | |
| DAG relaxation (topological order) | Any, graph must be a DAG | Yes (no cycles possible) | No | |
| A* | Non-negative, plus an admissible heuristic | No | No (single pair) | Dijkstra's worst case; usually far fewer expansions |
| Johnson | Any, no negative cycle | Yes | Yes |
How to choose: unweighted → BFS; weights 0/1 → 0-1 BFS; DAG → relax in topological order; non-negative → Dijkstra (A* if you have a good lower bound on remaining distance, as in road maps — see the capstone); negative edges, one source → Bellman-Ford; all pairs on a small dense graph → Floyd-Warshall; all pairs on a large sparse graph with negative edges → Johnson. All are developed with full proofs in Shortest Paths.
Topological Sort
A linear ordering of vertices in a DAG (Directed Acyclic Graph) such that for every edge , comes before . Used for dependency resolution, build systems, course scheduling.
graph LR
A["Course A"] --> C["Course C"]
B["Course B"] --> C
B --> D["Course D"]
C --> E["Course E"]
D --> E
Topological order: A, B, C, D, E (or A, B, D, C, E — not unique).
Intuition. Something with no prerequisites can go first. Remove it, and something else now has no remaining prerequisites. Kahn's algorithm is that idea with a counter per vertex (its in-degree among the vertices not yet output). The DFS algorithm comes at it from the other end: the first vertex DFS finishes has nothing left to explore after it, so it can go last.
A topological order exists if and only if the graph is a DAG. If there is a cycle , each vertex would have to come before the next and so before itself. Conversely, every finite DAG has a source (a vertex with in-degree 0) — walk backwards along incoming edges; without a cycle you cannot walk forever among finitely many vertices, so you stop at a vertex with no incoming edge — and putting that source first and recursing on the rest builds an order. That constructive proof is Kahn's algorithm.
Kahn's Algorithm (BFS-based)
TypeScript:
function topologicalSort(graph: AdjList, numNodes: number): number[] {
const inDegree = new Array(numNodes).fill(0);
// Calculate in-degrees
for (const [_, neighbors] of graph) {
for (const neighbor of neighbors) {
inDegree[neighbor]++;
}
}
// Start with all nodes that have no incoming edges
const queue: number[] = [];
for (let i = 0; i < numNodes; i++) {
if (inDegree[i] === 0) queue.push(i);
}
const result: number[] = [];
while (queue.length > 0) {
const node = queue.shift()!;
result.push(node);
for (const neighbor of graph.get(node) || []) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
if (result.length !== numNodes) {
throw new Error("Graph has a cycle — topological sort impossible");
}
return result;
}
Python:
from collections import deque
def topological_sort(graph: dict[int, list[int]], num_nodes: int) -> list[int]:
in_degree = [0] * num_nodes
for neighbors in graph.values():
for neighbor in neighbors:
in_degree[neighbor] += 1
queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph.get(node, []):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != num_nodes:
raise ValueError("Graph has a cycle")
return result
Complexity: time, space.
Trace: Kahn's algorithm on the course graph
Courses A–E numbered 0–4, edges A→C, B→C, B→D, C→E, D→E. Initial in-degrees [A 0, B 0, C 2, D 1, E 2], initial queue [A, B]. One row per dequeue; computed by script.
| Step | Dequeue | In-degrees after (A, B, C, D, E) | Queue after | Output so far |
|---|---|---|---|---|
| 1 | A | 0, 0, 1, 1, 2 | [B] | A |
| 2 | B | 0, 0, 0, 0, 2 | [C, D] | A, B |
| 3 | C | 0, 0, 0, 0, 1 | [D] | A, B, C |
| 4 | D | 0, 0, 0, 0, 0 | [E] | A, B, C, D |
| 5 | E | 0, 0, 0, 0, 0 | [] | A, B, C, D, E |
All five vertices were output, so the graph is acyclic and the order is A, B, C, D, E. Had there been a cycle, the vertices on it would never reach in-degree 0 and the output would stop short — that is the cycle check.
Why Kahn is correct. Invariant: when a vertex is output, all of its predecessors have already been output. A vertex enters the queue only when its counter hits 0, i.e. after every edge into it has been "removed" by outputting its source. So every edge has before in the result. Completeness: if the graph is a DAG, the not-yet-output vertices always form a DAG, which has a source; that source has counter 0 and is in the queue, so the loop cannot stop early. If the graph has a cycle, no vertex on it can be output first (its predecessor on the cycle is still waiting), so none is ever output and len(result) < num_nodes.
The four-language version, with the same course graph and a three-vertex cycle:
from collections import deque
def topological_sort(graph: dict[int, list[int]], num_nodes: int) -> list[int]:
in_degree = [0] * num_nodes
for neighbors in graph.values():
for neighbor in neighbors:
in_degree[neighbor] += 1
queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph.get(node, []):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != num_nodes:
raise ValueError("Graph has a cycle")
return result
COURSES = {0: [2], 1: [2, 3], 2: [4], 3: [4]} # A..E = 0..4
order = topological_sort(COURSES, 5)
assert order == [0, 1, 2, 3, 4]
pos = {v: i for i, v in enumerate(order)}
assert all(pos[u] < pos[v] for u, vs in COURSES.items() for v in vs)
try:
topological_sort({0: [1], 1: [2], 2: [0]}, 3)
raise AssertionError("expected ValueError")
except ValueError:
pass
print("ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
public class TopoSort {
static List<Integer> topologicalSort(List<List<Integer>> g) {
int n = g.size();
int[] inDegree = new int[n];
for (List<Integer> nbrs : g) for (int v : nbrs) inDegree[v]++;
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.add(i);
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int u = queue.poll();
result.add(u);
for (int v : g.get(u)) if (--inDegree[v] == 0) queue.add(v);
}
if (result.size() != n) throw new IllegalStateException("Graph has a cycle");
return result;
}
static List<List<Integer>> build(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) g.get(e[0]).add(e[1]);
return g;
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
List<List<Integer>> courses = build(5, new int[][] {{0, 2}, {1, 2}, {1, 3}, {2, 4}, {3, 4}});
check(topologicalSort(courses).equals(List.of(0, 1, 2, 3, 4)));
boolean threw = false;
try {
topologicalSort(build(3, new int[][] {{0, 1}, {1, 2}, {2, 0}}));
} catch (IllegalStateException e) {
threw = true;
}
check(threw);
System.out.println("ok");
}
}
#include <cassert>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>
using Graph = std::vector<std::vector<int>>;
std::vector<int> topologicalSort(const Graph& g) {
const int n = static_cast<int>(g.size());
std::vector<int> inDegree(n, 0), result;
for (const auto& nbrs : g)
for (int v : nbrs) inDegree[v]++;
std::queue<int> q;
for (int i = 0; i < n; i++)
if (inDegree[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : g[u])
if (--inDegree[v] == 0) q.push(v);
}
if (static_cast<int>(result.size()) != n) throw std::runtime_error("Graph has a cycle");
return result;
}
Graph build(int n, const std::vector<std::pair<int, int>>& edges) {
Graph g(n);
for (auto [u, v] : edges) g[u].push_back(v);
return g;
}
int main() {
Graph courses = build(5, {{0, 2}, {1, 2}, {1, 3}, {2, 4}, {3, 4}});
assert((topologicalSort(courses) == std::vector<int>{0, 1, 2, 3, 4}));
bool threw = false;
try {
topologicalSort(build(3, {{0, 1}, {1, 2}, {2, 0}}));
} catch (const std::runtime_error&) {
threw = true;
}
assert(threw);
std::cout << "ok\n";
}
type AdjList = Map<number, number[]>;
function topologicalSort(graph: AdjList, numNodes: number): number[] {
const inDegree = new Array(numNodes).fill(0);
// Calculate in-degrees
for (const [_, neighbors] of graph) {
for (const neighbor of neighbors) {
inDegree[neighbor]++;
}
}
// Start with all nodes that have no incoming edges
const queue: number[] = [];
for (let i = 0; i < numNodes; i++) {
if (inDegree[i] === 0) queue.push(i);
}
const result: number[] = [];
while (queue.length > 0) {
const node = queue.shift()!;
result.push(node);
for (const neighbor of graph.get(node) || []) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
if (result.length !== numNodes) {
throw new Error("Graph has a cycle — topological sort impossible");
}
return result;
}
const COURSES: AdjList = new Map([[0, [2]], [1, [2, 3]], [2, [4]], [3, [4]]]); // A..E = 0..4
if (JSON.stringify(topologicalSort(COURSES, 5)) !== JSON.stringify([0, 1, 2, 3, 4])) throw new Error("order");
let threw = false;
try {
topologicalSort(new Map([[0, [1]], [1, [2]], [2, [0]]]), 3);
} catch {
threw = true;
}
if (!threw) throw new Error("cycle not detected");
console.log("ok");
Replacing the FIFO queue with a min-heap yields the lexicographically smallest topological order in — a common follow-up. Replacing it with a stack still gives a valid order, just a different one: Kahn's correctness never depended on the queue discipline, only on outputting counter-0 vertices.
DFS-based Topological Sort
Python:
def topological_sort_dfs(graph: dict[int, list[int]], num_nodes: int) -> list[int]:
visited = set()
result = []
def dfs(node: int) -> None:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
result.append(node) # add after all descendants are processed
for i in range(num_nodes):
if i not in visited:
dfs(i)
return result[::-1] # reverse the postorder
Trace: DFS finish order on the course graph
Outer loop A, B, C, D, E; computed by script.
| Event | Postorder list after |
|---|---|
| dfs(A) → dfs(C) → dfs(E); E finishes | E |
| C finishes | E, C |
| A finishes | E, C, A |
| outer loop: B unvisited; dfs(B) → C visited, dfs(D) → E visited; D finishes | E, C, A, D |
| B finishes | E, C, A, D, B |
| C, D, E already visited | — |
Reversed: B, D, A, C, E — a different valid order from Kahn's A, B, C, D, E. Check: A before C, B before C and D, C and D before E.
Why it works. For every edge in a DAG, finishes before . When DFS examines , vertex is white (then it becomes a descendant of and finishes first), black (already finished), or gray — but gray means is an ancestor of and the edge closes a cycle, impossible in a DAG. So reverse finish order puts before for every edge.
Correction: this version does not detect cycles
Unlike Kahn's algorithm, topological_sort_dfs above never checks for a cycle: on a cyclic graph it silently returns an ordering that violates some edge (the test below shows it). To detect cycles, use the three-colour DFS from the cycle-detection section and abort on a gray neighbour, or verify the output by checking every edge.
def topological_sort_dfs(graph: dict[int, list[int]], num_nodes: int) -> list[int]:
visited = set()
result = []
def dfs(node: int) -> None:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
result.append(node) # add after all descendants are processed
for i in range(num_nodes):
if i not in visited:
dfs(i)
return result[::-1] # reverse the postorder
def is_topological(graph: dict[int, list[int]], order: list[int]) -> bool:
pos = {v: i for i, v in enumerate(order)}
return all(pos[u] < pos[v] for u, vs in graph.items() for v in vs)
COURSES = {0: [2], 1: [2, 3], 2: [4], 3: [4]}
assert topological_sort_dfs(COURSES, 5) == [1, 3, 0, 2, 4] # B, D, A, C, E
assert is_topological(COURSES, topological_sort_dfs(COURSES, 5))
CYCLE = {0: [1], 1: [2], 2: [0]}
bad = topological_sort_dfs(CYCLE, 3) # no error raised...
assert len(bad) == 3 and not is_topological(CYCLE, bad) # ...but the order is invalid
print("ok")
Topological order is also the right order for dynamic programming on a DAG: longest path, number of paths, earliest start times in a project schedule (the critical path method). Process vertices in topological order and relax each out-edge once; that is shortest and longest paths, negative weights included — the topological sort lesson does this in detail.
Strongly Connected Components (SCCs)
In a directed graph, an SCC is a maximal set of vertices where every vertex is reachable from every other vertex.
Mutual reachability is an equivalence relation (reflexive, symmetric, transitive), so the SCCs partition the vertices. Collapse each SCC to a single vertex and you get the condensation, which is always a DAG: if two SCCs could reach each other, they would be one SCC. That is why SCCs matter. Any directed graph is "a DAG of strongly connected blobs", so questions like "which services are in a dependency cycle?" or "how few edges make the graph strongly connected?" become a topological-sort problem on the condensation.
flowchart LR
subgraph S1["SCC {0, 1, 2}"]
V0["0"] --> V1["1"]
V1 --> V2["2"]
V2 --> V0
end
subgraph S2["SCC {3, 4}"]
V3["3"] --> V4["4"]
V4 --> V3
end
V1 --> V3
Kosaraju's Algorithm
- Run DFS on original graph, push nodes to stack in finish order
- Transpose the graph (reverse all edges)
- Pop from stack, run DFS on transposed graph — each DFS gives one SCC
Python:
def kosaraju(graph: dict[int, list[int]], n: int) -> list[list[int]]:
# Step 1: DFS and push to stack in finish order
visited = set()
stack = []
def dfs1(node: int) -> None:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs1(neighbor)
stack.append(node)
for i in range(n):
if i not in visited:
dfs1(i)
# Step 2: Build transposed graph
transposed: dict[int, list[int]] = defaultdict(list)
for u in graph:
for v in graph[u]:
transposed[v].append(u)
# Step 3: DFS on transposed graph in reverse finish order
visited.clear()
sccs = []
def dfs2(node: int, component: list[int]) -> None:
visited.add(node)
component.append(node)
for neighbor in transposed.get(node, []):
if neighbor not in visited:
dfs2(neighbor, component)
while stack:
node = stack.pop()
if node not in visited:
component: list[int] = []
dfs2(node, component)
sccs.append(component)
return sccs
Complexity: time, space.
Trace: Kosaraju on the two-SCC graph
The graph in the diagram: 0→1, 1→2, 2→0, 1→3, 3→4, 4→3. Computed by script.
| Phase | What happens | Result |
|---|---|---|
| Pass 1 (DFS on from 0) | 0 → 1 → 2 (2 finishes: its only edge goes to 0, gray), then 1 → 3 → 4 (4 finishes), 3 finishes, 1 finishes, 0 finishes | finish stack (bottom to top): 2, 4, 3, 1, 0 |
| Transpose | : 1→0, 2→1, 0→2, 3→1, 4→3, 3→4 | — |
| Pass 2, pop 0 | DFS on from 0 reaches 2, then 1; from 1 the edge goes to 0 (visited). 3 is unreachable in from here | SCC [0, 2, 1] |
| Pops 1, 2 | already visited | — |
| Pass 2, pop 3 | DFS on from 3 reaches 4; 3→1 leads to visited 1 | SCC [3, 4] |
Why it works (sketch). Key lemma (CLRS 3rd ed., Lemma 22.14): if there is an edge from SCC to SCC , then the largest finish time in exceeds the largest finish time in . So the vertex with the overall largest finish time lies in a source SCC of the condensation. In every edge is reversed, so that SCC has no outgoing edges to other unvisited SCCs, and a DFS from it collects exactly that SCC. Removing it, the next-largest unvisited finish time is in a source of what remains, and so on. The connectivity lesson gives the full proof and Tarjan's one-pass algorithm, which finds the same components with a single DFS and a low-link value per vertex.
Self-checking (the block above uses defaultdict without importing it, which fails at runtime when step 2 runs; the import is added here):
from collections import defaultdict
def kosaraju(graph: dict[int, list[int]], n: int) -> list[list[int]]:
# Step 1: DFS and push to stack in finish order
visited = set()
stack = []
def dfs1(node: int) -> None:
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs1(neighbor)
stack.append(node)
for i in range(n):
if i not in visited:
dfs1(i)
# Step 2: Build transposed graph
transposed: dict[int, list[int]] = defaultdict(list)
for u in graph:
for v in graph[u]:
transposed[v].append(u)
# Step 3: DFS on transposed graph in reverse finish order
visited.clear()
sccs = []
def dfs2(node: int, component: list[int]) -> None:
visited.add(node)
component.append(node)
for neighbor in transposed.get(node, []):
if neighbor not in visited:
dfs2(neighbor, component)
while stack:
node = stack.pop()
if node not in visited:
component: list[int] = []
dfs2(node, component)
sccs.append(component)
return sccs
G = {0: [1], 1: [2, 3], 2: [0], 3: [4], 4: [3]}
assert kosaraju(G, 5) == [[0, 2, 1], [3, 4]]
assert sorted(map(sorted, kosaraju({0: [1], 1: [2], 2: [3]}, 4))) == [[0], [1], [2], [3]] # a DAG: all singletons
print("ok")
Note the order in which Kosaraju emits SCCs: a topological order of the condensation ({0, 1, 2} before {3, 4}, matching the edge 1 → 3). That is a free bonus used by 2-SAT.
Union-Find (Disjoint Set Union)
Union-Find tracks a set of elements partitioned into disjoint subsets. It supports two operations efficiently: find (which set does an element belong to?) and union (merge two sets).
Intuition. Each set is a tree of parent pointers, and the root is the set's name. find(x) walks up to the root; union(x, y) points one root at the other. Two tricks keep the trees flat. Union by rank hangs the shorter tree under the taller one, so height grows only when two equal-height trees merge. Path compression makes every node visited by find point straight at the root, so the next find on any of them is one step. Unlike BFS and DFS, Union-Find is online: edges can arrive one at a time, and connectivity queries can be interleaved with them, with no re-traversal.
flowchart BT
N1["1"] --> N0["0 (root, rank 1)"]
N2["2"] --> N0
N3["3"] --> N0
N4["4"] --> N0
The diagram is the forest after Try-It Problem 5: every vertex points directly at root 0.
With Path Compression + Union by Rank
TypeScript:
class UnionFind {
parent: number[];
rank: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
union(x: number, y: number): boolean {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX === rootY) return false; // already connected
// Union by rank
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true;
}
connected(x: number, y: number): boolean {
return this.find(x) === this.find(y);
}
}
Python:
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x: int, y: int) -> bool:
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
With both path compression and union by rank, operations are nearly — formally where is the inverse Ackermann function, which is effectively constant () for all practical input sizes.
The bound is amortized over a sequence of operations (Tarjan, 1975; Tarjan and van Leeuwen, 1984); a single find can still take steps the first time it walks a long path, after which that path is flat.
Trace: Try-It Problem 5 with the code above
Five vertices, edges (0,1), (0,2), (1,3), (2,3), (3,4). One row per union; computed by script.
| Operation | Roots found | Result | parent after | rank after | Components |
|---|---|---|---|---|---|
| (start) | — | — | [0, 1, 2, 3, 4] | [0, 0, 0, 0, 0] | 5 |
| union(0, 1) | 0, 1 | merge (equal rank: 1 under 0, rank[0] = 1) | [0, 0, 2, 3, 4] | [1, 0, 0, 0, 0] | 4 |
| union(0, 2) | 0, 2 | merge (2 under higher-rank 0) | [0, 0, 0, 3, 4] | [1, 0, 0, 0, 0] | 3 |
| union(1, 3) | 0, 3 | merge | [0, 0, 0, 0, 4] | [1, 0, 0, 0, 0] | 2 |
| union(2, 3) | 0, 0 | skip: same root, edge (2,3) closes a cycle | [0, 0, 0, 0, 4] | [1, 0, 0, 0, 0] | 2 |
| union(3, 4) | 0, 4 | merge | [0, 0, 0, 0, 0] | [1, 0, 0, 0, 0] | 1 |
One component, and the skipped union identified the redundant edge — that is exactly how Redundant Connection is solved.
Why the trees stay shallow. With union by rank alone (no compression), a root of rank has at least nodes in its tree. Induction: a rank-0 root has itself. A root reaches rank only when two rank- roots merge, giving at least nodes; merging unequal ranks keeps the larger rank and only adds nodes. Since a tree has at most nodes, , so every rank — and the height, which rank bounds — is at most . That alone gives per operation. Path compression on top brings the amortized cost down to ; the proof is long (CLRS 3rd ed., Section 21.4) and the Union-Find lesson gives the intuition. For calibration: for every below a number with far more digits than there are atoms in the observable universe.
The four-language version. Tests: Try-It Problem 5 (union results and component count) and a disconnected case.
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x: int, y: int) -> bool:
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
uf = UnionFind(5)
results = [uf.union(u, v) for u, v in [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]]
assert results == [True, True, True, False, True]
assert len({uf.find(i) for i in range(5)}) == 1
assert uf.parent == [0, 0, 0, 0, 0] and uf.rank == [1, 0, 0, 0, 0]
uf2 = UnionFind(4)
uf2.union(0, 1)
assert uf2.connected(0, 1) and not uf2.connected(1, 2)
assert len({uf2.find(i) for i in range(4)}) == 3
print("ok")
import java.util.HashSet;
import java.util.Set;
public class UnionFindDemo {
static final class UnionFind {
final int[] parent;
final int[] rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != root) { // iterative path compression
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false;
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
return true;
}
boolean connected(int x, int y) { return find(x) == find(y); }
int components() {
Set<Integer> roots = new HashSet<>();
for (int i = 0; i < parent.length; i++) roots.add(find(i));
return roots.size();
}
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
boolean[] expected = {true, true, true, false, true};
for (int i = 0; i < edges.length; i++) check(uf.union(edges[i][0], edges[i][1]) == expected[i]);
check(uf.components() == 1);
UnionFind uf2 = new UnionFind(4);
uf2.union(0, 1);
check(uf2.connected(0, 1) && !uf2.connected(1, 2) && uf2.components() == 3);
System.out.println("ok");
}
}
#include <cassert>
#include <iostream>
#include <numeric>
#include <set>
#include <utility>
#include <vector>
class UnionFind {
public:
explicit UnionFind(int n) : parent_(n), rank_(n, 0) { std::iota(parent_.begin(), parent_.end(), 0); }
int find(int x) {
int root = x;
while (parent_[root] != root) root = parent_[root];
while (parent_[x] != root) { // iterative path compression
int next = parent_[x];
parent_[x] = root;
x = next;
}
return root;
}
bool unite(int x, int y) { // "union" is a C++ keyword
int rx = find(x), ry = find(y);
if (rx == ry) return false;
if (rank_[rx] < rank_[ry]) std::swap(rx, ry);
parent_[ry] = rx;
if (rank_[rx] == rank_[ry]) rank_[rx]++;
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
int components() {
std::set<int> roots;
for (int i = 0; i < static_cast<int>(parent_.size()); i++) roots.insert(find(i));
return static_cast<int>(roots.size());
}
private:
std::vector<int> parent_, rank_;
};
int main() {
UnionFind uf(5);
std::vector<std::pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
std::vector<bool> expected = {true, true, true, false, true};
for (std::size_t i = 0; i < edges.size(); i++) assert(uf.unite(edges[i].first, edges[i].second) == expected[i]);
assert(uf.components() == 1);
UnionFind uf2(4);
uf2.unite(0, 1);
assert(uf2.connected(0, 1) && !uf2.connected(1, 2) && uf2.components() == 3);
std::cout << "ok\n";
}
class UnionFind {
parent: number[];
rank: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
union(x: number, y: number): boolean {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX === rootY) return false; // already connected
// Union by rank
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true;
}
connected(x: number, y: number): boolean {
return this.find(x) === this.find(y);
}
}
const uf = new UnionFind(5);
const results = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]].map(([u, v]) => uf.union(u, v));
if (JSON.stringify(results) !== JSON.stringify([true, true, true, false, true])) throw new Error("unions");
if (new Set([0, 1, 2, 3, 4].map((i) => uf.find(i))).size !== 1) throw new Error("components");
const uf2 = new UnionFind(4);
uf2.union(0, 1);
if (!uf2.connected(0, 1) || uf2.connected(1, 2)) throw new Error("connected");
if (new Set([0, 1, 2, 3].map((i) => uf2.find(i))).size !== 3) throw new Error("components 2");
console.log("ok");
The Java and C++ versions compress paths iteratively (two passes: find the root, then repoint), because the recursive find in the Python and TypeScript versions recurses once per node on the path. With union by rank that depth is at most for elements, so recursion is safe there — but if you drop union by rank, a sequence of unions can build a path of length and the recursive find overflows the stack.
Union-Find Applications
- Connected components: Run union on all edges, count distinct roots
- Cycle detection in undirected graphs: If
find(u) == find(v)before unioning edge , there is a cycle - Kruskal's MST: Sort edges by weight, union them greedily
- Consistent Hashing: Track which nodes own which partitions
Correction: consistent hashing does not use Union-Find
The last bullet is inaccurate. Consistent hashing places nodes and keys on a hash ring and assigns each key to the next node clockwise; the data structure behind it is a sorted array or balanced tree of ring positions searched by binary search, not a disjoint-set forest (see the consistent hashing page). Real applications of Union-Find include connected-component labelling of images (pixels joined to equal-coloured neighbours), unification in Hindley-Milner type inference, percolation simulations, grouping duplicate records ("these two accounts share an email, so they are the same person"), and Kruskal.
Minimum Spanning Tree (MST)
A spanning tree of a connected undirected graph is a subset of edges that connects all vertices without a cycle. A minimum spanning tree has the smallest total weight. Think of laying cable between buildings: you need everything connected, you never need a redundant loop, and you want to spend as little as possible.
Two facts drive every MST algorithm. The cut property: for any split of the vertices into two non-empty sides, a lightest edge crossing the split belongs to some MST. The cycle property: a strictly heaviest edge on any cycle belongs to no MST.
Proof of the cut property (exchange argument). Let be a lightest edge crossing cut and let be an MST that does not contain . Adding to creates exactly one cycle. That cycle crosses the cut at , so it must cross back somewhere: there is another edge on it crossing the cut. is still a spanning tree (we removed an edge from the only cycle), and because is lightest across the cut. So is also an MST, and it contains .
Kruskal's Algorithm
Sort all edges by weight, then greedily add each edge if it doesn't create a cycle (using Union-Find).
Python:
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
"""Returns MST edges. edges: [(u, v, weight), ...]"""
edges.sort(key=lambda e: e[2])
uf = UnionFind(n)
mst = []
for u, v, w in edges:
if uf.union(u, v):
mst.append((u, v, w))
if len(mst) == n - 1:
break
return mst
Complexity: time (dominated by sorting), space.
Why Kruskal is correct. When Kruskal accepts edge , and are in different components; take = the component of . No previously accepted edge crosses (it is a component), and every lighter edge crossing would already have been accepted, so is a lightest edge across that cut, and the cut property says it is safe. Rejected edges join two vertices already connected by lighter edges, so they are the heaviest on a cycle. By induction, the accepted edges are always a subset of some MST, and at the end they span the graph.
Trace: Kruskal on the Dijkstra graph, undirected
Treat the Dijkstra example as undirected: A–B 4, A–C 1, B–D 1, C–D 5, C–B 2 (A..D = 0..3). Edges sorted by weight; computed by script.
| Edge | Weight | find(u) ≠ find(v)? | Action | MST weight so far |
|---|---|---|---|---|
| A–C | 1 | yes | accept | 1 |
| B–D | 1 | yes | accept | 2 |
| C–B | 2 | yes ({A, C} vs {B, D}) | accept: 3 = edges, stop | 4 |
| A–B | 4 | (not examined) | — | — |
| C–D | 5 | (not examined) | — | — |
MST weight 4: A–C, B–D, C–B. Note that the MST is not the shortest-path tree from A: the shortest-path tree uses the same three edges here by coincidence, but in general an MST minimises total weight, not distance from any one vertex.
Self-checking version (the block above needs UnionFind defined; it is repeated here, and the input is copied before sorting because edges.sort mutates the caller's list — a pitfall when the same edge list is reused):
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
"""Returns MST edges. edges: [(u, v, weight), ...]"""
edges.sort(key=lambda e: e[2])
uf = UnionFind(n)
mst = []
for u, v, w in edges:
if uf.union(u, v):
mst.append((u, v, w))
if len(mst) == n - 1:
break
return mst
E = [(0, 1, 4), (0, 2, 1), (1, 3, 1), (2, 3, 5), (2, 1, 2)]
mst = kruskal(4, list(E)) # pass a copy: kruskal sorts in place
assert mst == [(0, 2, 1), (1, 3, 1), (2, 1, 2)]
assert sum(w for _, _, w in mst) == 4
# A disconnected graph has no spanning tree: Kruskal returns a forest with < n-1 edges.
assert len(kruskal(4, [(0, 1, 1), (2, 3, 1)])) == 2
print("ok")
Prim's algorithm is the other classic: grow a single tree from any start vertex, always adding the lightest edge from the tree to a non-tree vertex — Dijkstra's loop with "edge weight" in place of "distance from the source". With a binary heap it is ; with an array, , which is the better choice on dense graphs. Both, plus Borůvka's parallel-friendly algorithm, are in Minimum Spanning Trees.
Complexity summary
| Algorithm | Time | Extra space | Needs |
|---|---|---|---|
| Build adjacency list | — | ||
| BFS / DFS (list) | ( for push-all iterative DFS) | — | |
| BFS / DFS (matrix) | — | ||
| Bipartite check | undirected | ||
| Three-colour cycle detection | directed | ||
| Dijkstra, binary heap | heap entries | weights | |
| Dijkstra, array | weights , dense graph | ||
| Bellman-Ford | no reachable negative cycle | ||
| Floyd-Warshall | no negative cycle | ||
| Kahn / DFS topological sort | DAG | ||
| Kosaraju SCC | (transpose) | directed | |
| Union-Find, operations | amortized | — | |
| Kruskal | + the sort | undirected |
Constants matter more than the table suggests. A BFS over a CSR array scans memory sequentially and can process on the order of edges per second in C++; the same BFS over a dict of Python lists is one to two orders of magnitude slower. Dijkstra's cost is dominated by heap operations, each a few cache misses, which is why routing engines precompute (see the capstone's reading on contraction hierarchies) rather than make Dijkstra itself faster.
Real-world uses
- Internet routing. Link-state protocols (OSPF, IS-IS) flood the topology to every router, and each router runs Dijkstra — "shortest path first" — with itself as the source to fill its forwarding table. Distance-vector protocols (RIP) are a distributed Bellman-Ford, which is where the count-to-infinity problem comes from. BGP is a path-vector protocol that picks routes by policy rather than by shortest path. See network layer and BGP.
- Maps and navigation. Road networks are sparse weighted graphs with tens of millions of vertices. Production routers (OSRM, GraphHopper, Valhalla and the commercial engines) do not run plain Dijkstra per query; they precompute speed-up structures such as contraction hierarchies or multi-level partitions, and A* with a geometric heuristic is the textbook first step. The capstone builds the first two rungs of that ladder; spatial indexing covers how the start coordinate is snapped to the nearest road.
- Build systems and package managers. Make, Bazel, Gradle and every CI pipeline topologically sort a dependency DAG before running anything, and report a cycle when they cannot. Python ships Kahn's algorithm in the standard library as
graphlib.TopologicalSorter(since 3.9). Spreadsheets recalculate cells in dependency order and report circular references. - Garbage collection. The mark phase of a tracing collector is reachability from the root set — BFS or DFS over the object graph. Cheney's copying collector is a BFS that uses the to-space itself as the queue.
- Databases. Deadlock detectors build a wait-for graph (transaction A waits for a lock held by B) and look for a cycle; query optimisers search join orders over a join graph (query planning); graph databases store adjacency directly so traversals avoid index lookups per hop (graph databases).
- Compilers. Control-flow graphs, dominator trees and SCCs of the call graph (to find mutually recursive functions); register allocation is graph colouring on an interference graph; instruction scheduling is a topological order of a dependency DAG.
- Distributed systems. Gossip protocols spread state over a random graph and their convergence time is a graph property (gossip protocols); causality between events is a DAG (vector clocks); Git's history is a commit DAG, and
git merge-basesearches it for a best common ancestor. - Social and web graphs. "People you may know" starts from friends-of-friends (BFS to depth 2); PageRank is a random walk on the link graph; web crawlers are BFS with a politeness-limited frontier. Covered in Graph Algorithms in the Real World.
Pitfalls & edge cases
- Forgetting disconnected graphs. Running BFS/DFS from vertex 0 only covers 0's component. Component counting, bipartiteness, cycle detection and topological sort all need the outer loop over every vertex.
- Marking visited too late. In BFS, mark on enqueue. Marking on dequeue lets a vertex be enqueued once per incoming edge — still correct for distances, but queue entries and much slower on dense graphs.
- Recursion depth. Recursive DFS on a 100,000-vertex path overflows Python's default limit of 1,000 and usually the JVM's default thread stack. Use the explicit-stack form or raise the limit deliberately (
sys.setrecursionlimitplusthreading.stack_sizein Python). - Undirected edges added once. For an undirected graph, add both and . Forgetting one direction gives a directed graph with silently wrong answers.
- Treating the parent as a cycle. In undirected cycle detection, the edge back to the vertex you came from is not a cycle. But with parallel edges (two distinct edges between the same pair), it is — skip the parent edge id, not the parent vertex.
- Two colours for directed cycles. "Already visited" means a cycle only in undirected graphs. In directed graphs you need gray versus black (the diamond test above).
- Dijkstra with negative weights, or with a "finalized" check that fires on push instead of on pop. Also: comparing the popped distance to the stored one (
if d > dist[u]: continue) is not optional — without it, stale entries re-relax edges and the running time degrades. - Overflow.
INT_MAX + wwraps negative in Java and C++. Uselong/long longdistances, and guard relaxations withdist[u] != INF. Path weights on large graphs exceed easily: edges of weight sum to . - Vertex labels that are not . Strings, coordinates, or 1-indexed input. Map them to indices once, or use a dict-based graph throughout — mixing both is a classic source of off-by-one bugs.
- Self-loops and duplicate edges. A self-loop is a cycle (Kahn never outputs that vertex; three-colour DFS finds it immediately). Duplicate edges double-count in-degrees correctly in Kahn, but break Floyd-Warshall's initialisation (see the correction above).
- Mutating inputs.
kruskalsorts the caller's list in place;defaultdictcreates keys when you merely readgraph[v]. Both surprise callers who reuse the structure. - Topological order is not unique. Tests that compare against one specific order are wrong unless the problem pins the order (for example, "lexicographically smallest"). Verify with an edge check instead.
Variations
- 0-1 BFS. Weights 0 or 1: a deque, pushing 0-edges to the front and 1-edges to the back. . In BFS in Depth.
- Bidirectional BFS / Dijkstra. Search from both ends and stop when the frontiers meet; on graphs with branching factor and distance this explores roughly instead of vertices. The capstone's stretch goal.
- A*. Dijkstra ordered by , where is a lower bound on the remaining distance (an admissible heuristic). Same answer, fewer expansions when is good. In Shortest Paths and the capstone.
- Iterative deepening DFS. DFS with a depth limit 0, 1, 2, …: BFS's optimality with DFS's memory, for huge implicit graphs (game trees, puzzles).
- Tarjan's SCC and low-link algorithms. One DFS finds SCCs, bridges and articulation points by tracking the earliest-discovered vertex reachable from each subtree. In Connectivity.
- Weighted / rollback Union-Find. Store an offset to the parent (for "A is 3 more than B" constraints) or skip path compression so unions can be undone (offline dynamic connectivity). In Union-Find in Depth.
- Prim and Borůvka. The other two MST algorithms; Borůvka's rounds parallelise well and underlie the fastest theoretical MST algorithms.
- Johnson's algorithm. One Bellman-Ford to compute potentials that make all weights non-negative, then Dijkstras: all pairs in on sparse graphs with negative edges.
- Euler tours, matchings, flows, 2-SAT. The rest of the module: Euler paths, matching, network flow, 2-SAT.
Practice Problems
| Problem | Algorithm | Difficulty |
|---|---|---|
| Number of Islands | BFS/DFS flood fill | Medium |
| Clone Graph | BFS/DFS + hash map | Medium |
| Course Schedule | Topological sort (cycle detection) | Medium |
| Course Schedule II | Topological sort (ordering) | Medium |
| Network Delay Time | Dijkstra | Medium |
| Cheapest Flights Within K Stops | Modified Bellman-Ford | Medium |
| Redundant Connection | Union-Find | Medium |
| Word Ladder | BFS | Hard |
| Alien Dictionary | Topological sort | Hard |
| Critical Connections in a Network | Tarjan's bridges | Hard |
Practice ladder
Fifteen problems in order of difficulty, with links. Each line says what the problem teaches in our words; open the link for the real statement. Problems 1–10 cover this page; 11–15 bridge into the deep lessons.
- Find if Path Exists in Graph (LeetCode 1971) — Easy. Build an adjacency list from an edge list and answer one reachability query; do it with BFS, DFS and Union-Find.
Hint
Any traversal from the source that reaches the destination answers yes. With Union-Find, union every edge and compare roots.
- Find the Town Judge (LeetCode 997) — Easy. No traversal at all: the answer is a vertex with in-degree and out-degree 0.
Hint
Keep one counter per person: +1 for each incoming trust, −1 for each outgoing one. The judge is the person whose counter is .
- Number of Islands (LeetCode 200) — Medium. Counting connected components in an implicit grid graph.
Hint
Scan every cell; each time you find unvisited land, increment the count and flood-fill its island so it is never counted again.
Solution
from collections import deque
def num_islands(grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1" or seen[r][c]:
continue
count += 1
seen[r][c] = True
q = deque([(r, c)])
while q: # BFS: no recursion-depth issue
x, y = q.popleft()
for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1" and not seen[nx][ny]:
seen[nx][ny] = True
q.append((nx, ny))
return count
g1 = [list("11110"), list("11010"), list("11000"), list("00000")]
g2 = [list("11000"), list("11000"), list("00100"), list("00011")]
assert num_islands(g1) == 1 and num_islands(g2) == 3
assert num_islands([list("0")]) == 0
print("ok")
time and space: every cell is enqueued at most once and has four neighbours.
- Rotting Oranges (LeetCode 994) — Medium. Multi-source BFS: all initially rotten cells start at distance 0, and the answer is the largest distance (or −1 if some fresh cell is unreachable).
Hint
Enqueue every rotten cell before the loop; process level by level and count levels; at the end check that no fresh orange remains.
- Clone Graph (LeetCode 133) — Medium. Traversal plus a hash map from original node to copy; the map doubles as the visited set and is what makes cycles safe.
Hint
Create a node's copy the moment you first see it (on enqueue), store it in the map, then wire up neighbour lists as you process each node.
- Is Graph Bipartite? (LeetCode 785) — Medium. The two-colouring from this page, including the outer loop for disconnected inputs.
Hint
BFS colouring from every uncoloured vertex; a neighbour with your own colour means an odd cycle.
- Course Schedule (LeetCode 207) — Medium. Cycle detection in a directed graph, phrased as "can everything be finished?"
Hint
Kahn's algorithm: if fewer than numCourses vertices are ever output, there is a cycle. Watch the edge direction — a pair [a, b] means must come before .
Solution
from collections import deque
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(num_courses)]
indeg = [0] * num_courses
for course, pre in prerequisites: # edge pre -> course
graph[pre].append(course)
indeg[course] += 1
q = deque(i for i in range(num_courses) if indeg[i] == 0)
done = 0
while q:
u = q.popleft()
done += 1
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return done == num_courses
assert can_finish(2, [[1, 0]])
assert not can_finish(2, [[1, 0], [0, 1]])
assert can_finish(3, [])
assert not can_finish(1, [[0, 0]]) # a self-loop is a cycle
print("ok")
time and space.
- Course Schedule (CSES 1679) — Medium. Output an actual topological order (or report that none exists) under tight limits, with 1-indexed input.
Hint
Kahn's algorithm with arrays instead of dicts; print "IMPOSSIBLE" when the output is short. Any valid order is accepted.
- Redundant Connection (LeetCode 684) — Medium. Union-Find cycle detection: the first edge whose endpoints already share a root is the answer.
Hint
Process edges in order; union returns false exactly for the edge that closes a cycle. The problem asks for the last such edge in input order, and since the graph is a tree plus one edge there is exactly one.
Solution
def find_redundant_connection(edges: list[list[int]]) -> list[int]:
parent = list(range(len(edges) + 1)) # vertices are 1..n
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for u, v in edges:
ru, rv = find(u), find(v)
if ru == rv:
return [u, v]
parent[ru] = rv
return []
assert find_redundant_connection([[1, 2], [1, 3], [2, 3]]) == [2, 3]
assert find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) == [1, 4]
print("ok")
in practice; this version uses path halving (a one-pass form of compression) without union by rank, which is still amortized per operation.
- Network Delay Time (LeetCode 743) — Medium. Single-source Dijkstra; the answer is the largest finite distance, or −1 if anything is unreachable.
Hint
Run Dijkstra from the source, then take the max over all <span class="math" data-tex="n"></span> vertices; an unreached vertex means −1.
Solution
```python
import heapq
def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
dist = [float("inf")] * (n + 1)
dist[k] = 0
pq = [(0, k)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (d + w, v))
best = max(dist[1:])
return -1 if best == float("inf") else int(best)
assert network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) == 2
assert network_delay_time([[1, 2, 1]], 2, 1) == 1
assert network_delay_time([[1, 2, 1]], 2, 2) == -1
print("ok")
```
<span class="math" data-tex="O((V + E) \log V)"></span>.
- Shortest Routes I (CSES 1671) — Medium. Dijkstra at scale ( vertices, edges, weights up to ): forces 64-bit distances, the stale-entry check and fast I/O.
Hint
Path lengths reach about <span class="math" data-tex="10^{14}"></span>, so 32-bit integers overflow. If your solution times out, check that you skip stale heap entries.
- Cheapest Flights Within K Stops (LeetCode 787) — Medium. A hop limit breaks plain Dijkstra; Bellman-Ford limited to rounds is the clean solution.
Hint
Run <span class="math" data-tex="k + 1"></span> rounds of relaxation, but relax from a **copy** of the previous round's distances, so a single round cannot chain several edges together.
- Word Ladder (LeetCode 127) — Hard. An implicit graph on words; BFS for the fewest transformations, with a bucketing trick to find neighbours fast.
Hint
Never compare all pairs of words. Map each wildcard pattern like `h*t` to the words that match it; the neighbours of a word are the other words in its patterns' buckets.
Solution
```python
from collections import defaultdict, deque
def ladder_length(begin: str, end: str, words: list[str]) -> int:
word_set = set(words)
if end not in word_set:
return 0
buckets: dict[str, list[str]] = defaultdict(list)
for w in word_set | {begin}:
for i in range(len(w)):
buckets[w[:i] + "*" + w[i + 1:]].append(w)
dist = {begin: 1}
q = deque([begin])
while q:
w = q.popleft()
if w == end:
return dist[w]
for i in range(len(w)):
key = w[:i] + "*" + w[i + 1:]
for nxt in buckets[key]:
if nxt not in dist:
dist[nxt] = dist[w] + 1
q.append(nxt)
buckets[key] = [] # each bucket is expanded once
return 0
words = ["hot", "dot", "dog", "lot", "log", "cog"]
assert ladder_length("hit", "cog", words) == 5
assert ladder_length("hit", "cog", words[:-1]) == 0
print("ok")
```
With <span class="math" data-tex="N"></span> words of length <span class="math" data-tex="L"></span>: <span class="math" data-tex="O(N L^2)"></span> to build the buckets (each key is a length-<span class="math" data-tex="L"></span> string) and the same for the BFS, since each bucket is expanded once.
- Planets and Kingdoms (CSES 1683) — Hard. Label every vertex with its strongly connected component — Kosaraju or Tarjan on vertices, so the DFS must be iterative in most languages.
Hint
Kosaraju's two passes give component ids directly; number the components in the order the second pass discovers them.
- Critical Connections in a Network (LeetCode 1192) — Hard. Bridges via Tarjan's low-link values; the preview of the connectivity lesson.
Hint
During DFS, `low[v]` is the earliest discovery time reachable from <span class="math" data-tex="v"></span>'s subtree using at most one back edge. A tree edge <span class="math" data-tex="u \to v"></span> is a bridge exactly when `low[v] > disc[u]`.
Common mistakes & interview follow-ups
"Why BFS and not DFS for shortest path?" BFS processes vertices in non-decreasing distance order (the queue invariant), so the first time it reaches a vertex is along a shortest path. DFS's first arrival can be along any path.
"What if the graph does not fit in memory?" For implicit graphs (puzzles, word ladders), generate neighbours on the fly and store only the visited set; if even that is too large, use iterative deepening (memory ) or bidirectional search (roughly square-root the frontier). For huge explicit graphs, use CSR on disk with memory mapping, or external-memory / distributed BFS (level-synchronous BFS is how graph-processing systems such as Pregel-style frameworks run it).
"Edges arrive as a stream — keep answering 'are u and v connected?'" Union-Find, per operation. If edges can also be deleted, it gets much harder: offline, use divide and conquer over time with a rollback DSU; online, fully dynamic connectivity structures exist with polylogarithmic amortized bounds.
"Dijkstra with a decrease-key heap or with lazy deletion?" Lazy deletion (push duplicates, skip stale pops) is simpler, works with any library heap, and costs heap entries instead of . Decrease-key needs an indexed heap. Both are ; lazy is usually as fast or faster in practice.
"What if weights are negative?" Bellman-Ford for one source; Johnson's reweighting for all pairs. Negative cycles mean "shortest path" is undefined for anything that can reach one; report them.
"How would you find the shortest path that visits a set of k special vertices?" Shortest paths between the special vertices (k Dijkstras), then bitmask DP over subsets — . Visiting every vertex is the travelling salesman problem, NP-hard; see the Euler & Hamiltonian lesson.
"How do you detect a cycle in an undirected versus a directed graph?" Undirected: DFS with parent-skipping, or Union-Find. Directed: three-colour DFS (gray neighbour) or Kahn's leftover count. A plain "visited" check is wrong for directed graphs.
"Can you find the topological order with the smallest lexicographic value?" Kahn with a min-heap instead of a queue.
"Recursion is too deep — convert your DFS." Use an explicit stack of (vertex, next-neighbour index) frames, as in the Java and C++ finishOrder above; record finish times when a frame is exhausted.
"How do you reconstruct the path, not just the distance?" Store parent[v] when you set dist[v], then walk back from the target and reverse. All the four-language implementations above do this.
Common mistakes interviewers watch for: not handling disconnected graphs; using DFS for unweighted shortest paths; marking visited on dequeue; forgetting the stale check in Dijkstra; integer overflow in distances; building the graph with the wrong edge direction (prerequisite pairs are the classic trap).
Further Reading
- Trees — trees are acyclic connected graphs
- Dynamic Programming — shortest path problems as DP
- Consistent Hashing — graph/ring-based distribution
- Backtracking & Recursion — DFS-based exhaustive search
More from Archon:
- Greedy Algorithms — MSTs and the exchange argument from another angle
- Advanced Data Structures — DSU and other structures used inside graph algorithms
- Heaps & Priority Queues — the heap inside Dijkstra and Prim
- Matrices & Grids — grids as implicit graphs
- Network layer — OSPF's Dijkstra and RIP's Bellman-Ford worked step by step
- Graph databases — storing and querying graphs in production
Sources:
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed. — Ch. 22 (BFS, DFS, topological sort, SCCs), Ch. 21 (disjoint sets), Ch. 23 (MST), Ch. 24 (single-source shortest paths), Ch. 25 (all pairs). In the 4th edition these are Ch. 19–23.
- Sedgewick and Wayne, Algorithms, 4th ed. — Ch. 4 (graphs), with excellent diagrams of DFS and Kosaraju.
- Skiena, The Algorithm Design Manual, 3rd ed. — Ch. 7–8 (graph traversal and weighted graphs), and the catalogue of graph problems in Part II.
- cp-algorithms.com — BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, topological sort, SCC, DSU.
- E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1 (1959) — the shortest-path and MST algorithms in three pages.
- A. B. Kahn, "Topological sorting of large networks", Communications of the ACM 5(11) (1962).
- R. E. Tarjan, "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1(2) (1972); "Efficiency of a good but not linear set union algorithm", Journal of the ACM 22(2) (1975).
- Python documentation,
graphlib.TopologicalSorter.
Course navigation. Previous: Capstone: A Range-Query Engine (end of Module 3). Next: Graph Modeling & Implicit Graphs. Module map: the table at the top of this page. Course: DSA: Zero to Mastery.
Try It Yourself
Problem 1: Given a graph with edges [(0,1), (0,2), (1,2), (2,3)] and 4 nodes, find the shortest path from node 0 to node 3 (unweighted).
Solution
Use BFS starting from node 0:
- Level 0: visit 0, enqueue neighbors 1, 2
- Level 1: visit 1 (neighbor 2 already visited), visit 2 (enqueue 3)
- Level 2: visit 3 Shortest path distance: 2 (path: 0 -> 2 -> 3)
Problem 2: Determine if the directed graph with edges [(0,1), (1,2), (2,0)] and 3 nodes contains a cycle.
Solution
Use DFS with three-color marking (WHITE, GRAY, BLACK):
- Start DFS at 0: color 0 GRAY
- Visit 1: color 1 GRAY
- Visit 2: color 2 GRAY
- From 2, neighbor 0 is GRAY (still in the call stack) → back edge detected Answer: Yes, the graph contains a cycle (0 -> 1 -> 2 -> 0).
Problem 3: Perform topological sort on a DAG with edges: A->C, B->C, B->D, C->E, D->E.
Solution
Using Kahn's algorithm (BFS-based):
- In-degrees: A=0, B=0, C=2, D=1, E=2
- Start with queue: [A, B]
- Process A: reduce C's in-degree to 1. Process B: reduce C to 0, D to 0. Queue: [C, D]
- Process C: reduce E to 1. Process D: reduce E to 0. Queue: [E]
- Process E. One valid topological order: [A, B, C, D, E] (or [B, A, C, D, E] or [A, B, D, C, E], etc.)
Problem 4: Given a weighted graph with edges (A,B,4), (A,C,1), (C,B,2), (B,D,1), (C,D,5), find the shortest path from A to D using Dijkstra.
Solution
- Initialize: dist = {A:0, B:inf, C:inf, D:inf}, PQ = [(0,A)]
- Process A: update B=4, C=1. PQ = [(1,C), (4,B)]
- Process C: update B = min(4, 1+2) = 3, D = min(inf, 1+5) = 6. PQ = [(3,B), (4,B), (6,D)]
- Process B (dist=3): update D = min(6, 3+1) = 4. PQ = [(4,B), (4,D), (6,D)]
- Process D (dist=4): done. Shortest path A to D: 4 (path: A -> C -> B -> D)
Correction: the stale heap entries
The answer (4, via A → C → B → D) is right, but the walkthrough skips two pops. After processing B, the next entry popped is the stale (4, B) — B's distance is already 3, so it is discarded — and only then (4, D). If the search runs to completion rather than stopping at D, the last pop is the stale (6, D). See the Dijkstra trace table above, which lists all six pops.
Problem 5: Given 5 nodes and edges [(0,1), (0,2), (1,3), (2,3), (3,4)], use Union-Find to count the number of connected components.
Solution
Initialize: each node is its own component (5 components).
- Union(0,1): merge → 4 components
- Union(0,2): merge → 3 components
- Union(1,3): merge → 2 components
- Union(2,3): find(2)=0, find(3)=0 → already connected, skip
- Union(3,4): merge → 1 component Answer: 1 connected component
Quick Quiz
1. What is the time complexity of BFS on a graph represented as an adjacency list?
- a)
- b)
- c)
- d)
Answer
c) — BFS visits every vertex once () and examines every edge once () in an adjacency list representation.
2. Which shortest-path algorithm should you use if the graph has negative edge weights (but no negative cycles)?
- a) BFS
- b) Dijkstra
- c) Bellman-Ford
- d) Floyd-Warshall (if single-source only is needed)
Answer
c) Bellman-Ford — Dijkstra fails with negative weights because it assumes finalized distances cannot be improved. Bellman-Ford relaxes all edges times and handles negative weights correctly.
3. What does topological sort require about the graph?
- a) The graph must be undirected
- b) The graph must be a DAG (Directed Acyclic Graph)
- c) The graph must be weighted
- d) The graph must be connected
Answer
b) The graph must be a DAG (Directed Acyclic Graph) — Topological sort produces a linear ordering where for every edge , comes before . This is only possible when there are no cycles.
4. What is the amortized time complexity of Union-Find operations with both path compression and union by rank?
- a)
- b)
- c) (inverse Ackermann, effectively constant)
- d)
Answer
c) — The inverse Ackermann function grows so slowly that for all practical input sizes, making operations effectively constant time.
5. When is an adjacency matrix preferred over an adjacency list?
- a) When the graph is sparse
- b) When the graph is dense and you need edge lookup
- c) When you need to iterate over neighbors quickly
- d) When memory is limited
Answer
b) When the graph is dense and you need edge lookup — An adjacency matrix uses space, which is efficient for dense graphs where . It provides edge existence checks, whereas an adjacency list requires scanning the neighbor list.
6. A DFS on a directed graph examines an edge and finds colored BLACK (finished). What can you conclude?
- a) The graph has a cycle
- b) Nothing about cycles — it is a forward or cross edge
- c) is an ancestor of
- d) The graph is not connected
Answer
b) A black target means was fully explored earlier — a forward edge (if is a descendant of ) or a cross edge. Only a GRAY target (an ancestor still on the stack) indicates a cycle.
7. Why does Kruskal's algorithm produce a minimum spanning tree?
- a) It always picks the edge closest to the start vertex
- b) Every accepted edge is a lightest edge crossing some cut, so the cut property makes it safe
- c) It runs Dijkstra from every vertex
- d) Sorting guarantees there are no cycles
Answer
b) When Kruskal accepts , consider the cut between 's current component and everything else: is the lightest edge crossing it (any lighter crossing edge would already have been accepted), and the cut property says a lightest crossing edge belongs to some MST.