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 00 because 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

  1. 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

  1. 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

  1. 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.

  2. 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.

  3. 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 next matrix, and a lab showing the wrong loop order failing on 105 of 200 random graphs.

  4. 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

  1. 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

QuestionReach forCost
Is there any path from A to B?DFS or BFS
Shortest path, unweighted graph or gridBFS
Shortest path, non-negative weightsDijkstra
Shortest path, weights may be negativeBellman–Ford
Shortest path between every pairFloyd–Warshall
Shortest path with a known goal and a distance estimateA\*depends on the heuristic
All pairs, sparse graph, negative weightsJohnson’s — see lesson 04
A valid dependency orderTopological 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 costMST
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:

AlgorithmIs BFS/DFS with…
BFSa queue
DFSa stack
Dijkstraa min-heap keyed by distance
A*a min-heap keyed by distance plus an estimate of what remains
Prima min-heap keyed by edge weight, not path length
Kahn’s topological sorta 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

LessonWhat the lab demonstrates
connected componentsDFS, BFS and union-find agreeing on 400/400 random graphs; union-find beating a re-run traversal by ~500x when edges arrive incrementally
Bellman–FordDijkstra 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–Warshallthe 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.


↑ Back to Graphs