The procedures that answer questions about a graph, as opposed to the vocabulary that lets you state the question (lessons 01–04) or the two searches everything is built from (05-traversal).
These live here rather than in
03-algorithms/on purpose. The general rule in this course is that a procedure is filed under 03-algorithms. Graphs are the exception, because there are enough of these that they form their own body of knowledge, they all assume the same vocabulary, and every one of them is a modification of DFS or BFS rather than a fresh idea. Keeping them next to the structure they operate on is what makes that visible.For the general theory — what an algorithm is, how to count its cost, / / , recurrences and amortised analysis — go to 03-algorithms/01-complexity-analysis first. Everything below is quoted in that vocabulary and none of it is re-explained here.
Reading order
Start with lesson 00. It is numbered
00because it is the simplest algorithm here and the right first one to read — counting clusters is the first thing anyone does with a traversal.
Grouping
- Connected Components — [Intermediate] — how many separate clusters, and who is in each. Flood fill with DFS or BFS, union-find and the identity components = V − merges, why an isolated vertex counts, and the measured ~500× gap when edges arrive over time. Plus weak versus strong connectivity for directed graphs.
Ordering
- Topological Sort — [Intermediate] — a valid order for a set of dependencies. Kahn’s algorithm with in-degree counts, and the DFS variant that is just “decreasing finish time”. Both detect a cycle for free, and a cycle is exactly when no order exists.
Shortest paths
-
Dijkstra’s Algorithm — [Advanced] — the shortest path when edges have non-negative weights. BFS with the queue replaced by a min-heap, plus a lab showing it return where the true distance is on a graph with one negative edge.
-
Bellman–Ford — [Advanced] — shortest paths that survive negative weights, in , with no priority queue and no finalisation. Why rounds, and the extra pass that detects a negative cycle — including a lab where Dijkstra silently returns 3 for a distance that is really 1.
-
Floyd–Warshall — [Advanced] — every pair at once in , by permitting one more intermediate vertex per round. Negative cycles on the diagonal, path recovery via a
nextmatrix, and a lab showing the wrong loop order failing on 105 of 200 random graphs. -
A\* — [Advanced] — Dijkstra with the queue keyed on . Admissible versus consistent, building a heuristic by relaxing the problem, weighted A*, and tie-breaking — which takes the lab from 233 expanded cells to 38 for the identical path.
Structure
- Minimum Spanning Tree — [Advanced] — connecting everything at minimum total cost. Prim’s and Kruskal’s, the cut property that makes both correct, and why one wants a heap and the other a union-find.
Which algorithm answers which question
| Question | Reach for | Cost |
|---|---|---|
| Is there any path from A to B? | DFS or BFS | |
| Shortest path, unweighted graph or grid | BFS | |
| Shortest path, non-negative weights | Dijkstra | |
| Shortest path, weights may be negative | Bellman–Ford | |
| Shortest path between every pair | Floyd–Warshall | |
| Shortest path with a known goal and a distance estimate | A\* | depends on the heuristic |
| All pairs, sparse graph, negative weights | Johnson’s — see lesson 04 | |
| A valid dependency order | Topological sort | |
| Does a directed cycle exist? | DFS back edges, or Kahn’s leftover count | |
| Does an undirected cycle exist? | Union-find, or DFS ignoring the parent edge | |
| Connect everything at minimum total cost | MST | |
| How many separate clusters? | Connected components | |
| Which vertices are mutually reachable? | SCCs — lesson 00 |
The row that catches people out is the third versus the fourth. “Dijkstra is the shortest-path algorithm” is a half-truth; it is the shortest-path algorithm for non-negative weights, and it fails silently — returning a wrong number rather than an error — the moment that assumption breaks.
The pattern underneath all of them
Every algorithm in this folder is a traversal with one thing changed:
| Algorithm | Is BFS/DFS with… |
|---|---|
| BFS | a queue |
| DFS | a stack |
| Dijkstra | a min-heap keyed by distance |
| A* | a min-heap keyed by distance plus an estimate of what remains |
| Prim | a min-heap keyed by edge weight, not path length |
| Kahn’s topological sort | a queue, fed by vertices whose in-degree has dropped to zero |
Bellman–Ford and Floyd–Warshall are the two that break the pattern: they are dynamic programs over the graph rather than traversals — no frontier, no finalisation, just repeated relaxation — and that is exactly why they tolerate negative weights. A* is the opposite extreme: a traversal so aggressively steered that it may touch only a tenth of the graph.
What is verified
| Lesson | What the lab demonstrates |
|---|---|
| connected components | DFS, BFS and union-find agreeing on 400/400 random graphs; union-find beating a re-run traversal by ~500x when edges arrive incrementally |
| Bellman–Ford | Dijkstra returning 3 where the true distance is 1, silently; the bound being tight under a worst-case edge order and finishing in one round under a good one |
| Floyd–Warshall | the wrong loop order disagreeing with Bellman–Ford ground truth on 105 of 200 random graphs; negative cycles appearing on the diagonal |
| A\* | tie-breaking alone cutting expansions from 233 to 38; weighted A* trading a cost-18 path for a cost-20 one while halving the work; and admissibility violations at that do not yet cost optimality |
Question banks
One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.
- Connected Components
- Topological Sort
- Dijkstra’s Algorithm
- Bellman–Ford
- Floyd–Warshall
- A\* Search
- Minimum Spanning Tree
Related
- the graphs folder — the vocabulary and representations these assume
- traversal — DFS and BFS, which all of these modify
- complexity analysis — what means and how it was derived
- Heaps · Union-Find — the two structures these lean on
- 03-algorithms — the non-graph algorithms
Software engineering
Infrastructure & security
Computer science
Hardware & engineering