Graph Algorithms: BFS, DFS, Dijkstra, and Minimum Spanning Trees
Modelling a problem as a graph is usually the whole solution; after that, four classical algorithms cover most of what you need.
Leads to: 19.10 searches implicit graphs (the state graph you never build); the Euler Lab’s Graphs & Paths problems (grid path minimisation, network reduction) are direct applications.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Model a problem as a graph by naming the vertices, the edges, and the edge weights explicitly.
- Implement BFS and DFS and state exactly what each computes (\(O(V+E)\) each).
- Prove the greedy exchange argument behind Dijkstra and explain why negative edges break it.
- Implement Dijkstra with a binary heap in \(O((V+E)\log V)\) and handle the lazy-deletion detail correctly.
- Compute a minimum spanning tree with Kruskal (union–find) or Prim, and justify the cut property.
Key Vocabulary
- Graph
- \(G=(V,E)\); directed or not, weighted or not. In this phase the graph is often implicit: vertices are states, edges are moves.
- BFS
- Breadth-first search from a source; visits vertices in order of edge-count distance, giving shortest paths in UNWEIGHTED graphs. \(O(V+E)\).
- DFS
- Depth-first search; the natural tool for connectivity, cycle detection, topological order, and articulation points. \(O(V+E)\).
- Dijkstra
- Shortest paths from a source with NON-NEGATIVE weights: repeatedly settle the nearest unsettled vertex. \(O((V+E)\log V)\) with a binary heap.
- Minimum spanning tree
- A cycle-free subset of edges connecting all vertices with minimum total weight. Kruskal (sort + union–find) or Prim (grow with a heap).
- Cut property
- For any partition of \(V\) into two nonempty parts, the cheapest edge crossing the cut belongs to some MST. This one lemma proves both Kruskal and Prim.
- Union–find
- Disjoint-set structure with union by rank + path compression; near-constant \(\alpha(n)\) amortised per operation.
Intuition & Motivation
BFS and DFS: what each actually computes
BFS from \(s\) processes vertices in non-decreasing order of hop-count, so the first time it reaches \(v\) it has found a shortest (fewest-edges) path. That is only true when all edges have equal weight. DFS makes no distance guarantee at all; its value is the recursion structure - discovery/finish times, back edges (hence cycles), and topological ordering of a DAG.
| Problem | Algorithm | Cost |
|---|---|---|
| Shortest path, unweighted | BFS | \(O(V+E)\) |
| Shortest path, weights \(\ge0\) | Dijkstra + binary heap | \(O((V+E)\log V)\) |
| Shortest path, negative edges | Bellman–Ford (and it detects negative cycles) | \(O(VE)\) |
| Shortest path, DAG | Relax in topological order | \(O(V+E)\) |
| All pairs, small \(V\) | Floyd–Warshall | \(O(V^3)\) |
| Connectivity / cycles / topo-order | DFS | \(O(V+E)\) |
| Minimum spanning tree | Kruskal (union–find) or Prim (heap) | \(O(E\log E)\) |
Dijkstra: the greedy exchange argument
Minimum spanning trees
Kruskal applies the cut property in increasing weight order (union–find tells you whether an edge would close a cycle); Prim applies it to the cut between the grown tree and the rest. Both are the same lemma, differently scheduled.
Coding workbench
The Euler Lab’s Graphs & Paths problems are almost all of the form ‘minimise a cost through a grid or a network’ (Dijkstra or DP on a DAG) or ‘find the cheapest connected subnetwork’ (MST). The hard part is never the algorithm - it is noticing that the object in the problem statement is a graph.
- Using BFS for shortest paths in a WEIGHTED graph. It computes hop counts, not distances (unless every weight is equal).
- Running Dijkstra with negative edges. Use Bellman–Ford; Dijkstra’s exchange argument fails at the step \(\delta(s,y)\le\delta(s,u)\).
- Forgetting the if d > dist[u]: continue guard. The answer often survives, but the runtime degrades badly on dense graphs.
- Marking BFS vertices as visited at dequeue time instead of enqueue time - leads to duplicate queue entries and a quadratic blow-up.
- Implementing union–find without path compression or union by rank; the worst case degrades to \(O(n)\) per query and Kruskal becomes quadratic.
- Write the graph down as (vertex = ?, edge = ?, weight = ?) in words BEFORE you code. Ninety percent of graph bugs are modelling bugs.
- A grid is a graph with 4 (or 8) implicit edges per cell - do not build an edge list, just generate neighbours on the fly.
- 0–1 BFS (a deque, push-front for weight-0 edges) gives Dijkstra’s answer in \(O(V+E)\) when weights are only 0 or 1. Worth knowing.
- If the graph is a DAG (states only ever move ‘forward’), skip Dijkstra: relax in topological order for \(O(V+E)\). Most DP tables are exactly this.
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#11 Largest Product in a Grid (5%, tier A) #15 Lattice Paths (6%, tier A) #112 Bouncy Numbers (6%, tier A) #18 Maximum Path Sum I (7%, tier A)
Applied:
#504 Square on the Inside (16%, tier B) #577 Counting Hexagons (18%, tier B) #186 Connectedness of a Network (19%, tier B)
Challenge:
#161 Triominoes (41%, tier C) #184 Triangles Containing the Origin (41%, tier C)
160 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
(a) You are given an \(n\times n\) grid of positive costs and must move from the top-left to the bottom-right, paying the cost of each cell you enter, moving in all four directions. Which algorithm, and what is the complexity? What changes if you may only move right and down? (b) Prove that in a graph with distinct edge weights the MST is unique. (c) Show that Dijkstra with a heap is \(O(E\log V)\), not \(O(V^2)\), and say when the \(O(V^2)\) array version is actually better.
(a) Four-directional movement means the state graph has cycles, so it is a genuine shortest-path problem: Dijkstra with vertices = cells, edges = the ≤4 neighbours, weight = the cost of the cell being entered. Cost: \(V=n^2\), \(E\le4n^2\), so \(O(n^2\log n)\). If you may only move right and down, the state graph is a DAG (every move increases \(i+j\)), so you can relax in topological order - which is just the DP \(D[i][j]=c[i][j]+\min(D[i-1][j],\ D[i][j-1])\) - in \(O(n^2)\) with no heap at all. Recognising the DAG saves the log factor and a lot of code.
(b) Suppose \(T_1\ne T_2\) are both MSTs and all weights are distinct. Let \(e\) be the minimum-weight edge in exactly one of them, say \(e\in T_1\setminus T_2\). Adding \(e\) to \(T_2\) creates a cycle \(C\); since \(T_1\) is acyclic, some edge \(f\in C\) is not in \(T_1\). Then \(f\) is in exactly one of the trees too, so by the minimality of \(e\), \(w(e)\lt w(f)\) (strict, by distinctness). Swapping gives \(T_2-f+e\), a spanning tree of strictly smaller weight than \(T_2\) - contradicting that \(T_2\) is an MST. Hence \(T_1=T_2\).
(c) Each edge can trigger at most one push, so the heap holds \(O(E)\) entries and each push/pop costs \(O(\log E)=O(\log V^2)=O(2\log V)=O(\log V)\). Total \(O((V+E)\log V)\). The simple array version scans all \(V\) vertices to find the minimum each round: \(O(V^2+E)\). On a DENSE graph with \(E=\Theta(V^2)\), the array version’s \(O(V^2)\) beats the heap’s \(O(V^2\log V)\) - so for dense graphs, drop the heap.
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: In the step \(\delta(s,y)\le\delta(s,u)\) for the frontier vertex \(y\) on a shortest path to \(u\): the rest of the path can only add non-negative length. A negative edge invalidates it, so use Bellman–Ford.
A: For any cut, a minimum-weight crossing edge lies in some MST (exchange argument). It justifies Kruskal (apply it in increasing weight order) and Prim (apply it to the tree/rest cut).
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 2 & Ch. 7 - Modelling discipline - naming the entities and their relations before writing code - and the value of testing a graph routine against a brute-force path enumerator on small inputs.
- Additional Exercises for Convex Optimization (Boyd & Vandenberghe, 2016) current - Network / flow exercises - Shortest paths and MSTs as network-flow / combinatorial-optimization problems; the LP-duality view of why the greedy exchange argument works.
- Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lectures 32–33 - Complexity accounting for sparse structures (\(O(V+E)\) vs \(O(V^2)\)): the same sparsity thinking that governs matrix algorithms.