Graph Algorithms
How computers reason about networks of things — roads, friends, packets, dependencies. Ten algorithms, from the two traversals every other algorithm is built on, to weighted shortest paths, minimum spanning trees, and the heuristic search behind every modern pathfinder.
What is Graph Algorithms?
The 60-second primer
A graph is just dots and lines — but almost everything interesting in computer science is hiding inside one. The cities your maps app routes between. The friends in your social network. The packages your build system has to compile in the right order. The web pages Google's crawler walks. Once you see the world as a graph, a handful of algorithms unlock all of it.
The ten here split into four groups. Traversals — BFS and DFS — answer 'who can I reach from here, and in what order?' They are the seed of almost every other graph algorithm. Shortest paths — Dijkstra, Bellman-Ford, Floyd-Warshall — answer 'what's the cheapest route?' under different rules about edge weights. Minimum spanning trees — Union-Find, Kruskal, Prim — answer 'how do I connect every node for the least cost?' And A* answers the same shortest-path question, but with a hint about which direction to look first — the trick behind every modern pathfinder.
You do not need to memorise ten algorithms. You need to know which question each one answers and what assumption it requires. Once that's clear, the code follows in twenty lines. This topic walks you through them in the order they build on each other — traversals first, because everything else is a smarter traversal.
Where this shows up
- Maps and routing — Google Maps, Waze, and every GPS unit run Dijkstra or A* over a road graph millions of edges wide, every time you ask for directions.
- Build systems and schedulers —
make, Bazel, Webpack, Airflow, and CI pipelines all topologically sort their task DAG to decide what runs in parallel and what must wait. - Social networks and recommendations — friend-of-friend, shortest-path-between-people, and 'connected components' on follower graphs are all BFS or Union-Find under the hood.
- Networks and the internet — link-state routing protocols (OSPF, IS-IS) run Dijkstra on the network topology; distance-vector protocols (RIP, BGP path selection) trace back to Bellman-Ford.
- Game AI and robotics — every NPC that walks around a level, every robot vacuum that plans a path, runs A* on a grid or navmesh.
- Compilers and verifiers — register allocation is graph colouring; dead-code elimination is reachability; data-flow analysis runs a fixpoint over the control-flow graph.
- Crash detection and money laundering — anomaly detectors run connected-components and shortest-paths on transaction graphs to find rings of accounts moving money in circles.
Two ways to store a graph
An adjacency list keeps, for each node, the list of its neighbours — O(V + E) memory, fast iteration. An adjacency matrix is a V×V grid where M[u][v] is the edge weight (or ∞) — O(V²) memory, O(1) edge lookup. Lists win for sparse graphs (most real ones); matrices win for dense graphs and for algorithms like Floyd-Warshall that look up arbitrary edges in their inner loop.
Side-by-side
How they compare
The same concepts, on the same axes. Use this as a map; the individual pages are the territory.
| Algorithm | Solves | Time | Edge weights | Best for |
|---|---|---|---|---|
01BFS | Shortest path in edges | O(V + E) | Unweighted | Level-order walks; fewest-hops paths; shortest path in unweighted graphs. |
02DFS | Reachability / structure | O(V + E) | Unweighted | Cycle detection, topological order, connected components, maze backtracking. |
03Topological Sort | Linear DAG order | O(V + E) | DAG only | Build order, course prerequisites, task scheduling, dependency resolution. |
04Dijkstra | Single-source shortest path | O((V + E) log V) | Non-negative | Road maps, network routing, any weighted graph with positive costs. |
05Bellman-Ford | Single-source shortest path | O(V · E) | Negative OK; detects negative cycles | Currency arbitrage, distance-vector routing, graphs with negative weights. |
06Floyd-Warshall | All-pairs shortest path | O(V³) | Negative OK (no neg cycle) | Small dense graphs where every pair matters — transitive closure, network diameter. |
07Union-Find | Connectivity / merge sets | α(n) per op | n/a | Dynamic connectivity, Kruskal's cycle check, percolation, image segmentation. |
08Kruskal's MST | Minimum spanning tree | O(E log E) | Any (no neg cycle issues) | Sparse graphs; edges already sorted; when you have a fast DSU. |
09Prim's MST | Minimum spanning tree | O((V + E) log V) | Any | Dense graphs; when you have one starting vertex and want to grow outward. |
10A* | Single goal shortest path | O(E) with a good heuristic | Non-negative + heuristic | Pathfinding to a known target — games, GPS, robotics, anywhere geometry hints help. |
- Solves
- Shortest path in edges
- Time
- O(V + E)
- Edge weights
Unweighted- Best for
- Level-order walks; fewest-hops paths; shortest path in unweighted graphs.
- Solves
- Reachability / structure
- Time
- O(V + E)
- Edge weights
Unweighted- Best for
- Cycle detection, topological order, connected components, maze backtracking.
- Solves
- Linear DAG order
- Time
- O(V + E)
- Edge weights
DAG only- Best for
- Build order, course prerequisites, task scheduling, dependency resolution.
- Solves
- Single-source shortest path
- Time
- O((V + E) log V)
- Edge weights
Non-negative- Best for
- Road maps, network routing, any weighted graph with positive costs.
- Solves
- Single-source shortest path
- Time
- O(V · E)
- Edge weights
Negative OK; detects negative cycles- Best for
- Currency arbitrage, distance-vector routing, graphs with negative weights.
- Solves
- All-pairs shortest path
- Time
- O(V³)
- Edge weights
Negative OK (no neg cycle)- Best for
- Small dense graphs where every pair matters — transitive closure, network diameter.
- Solves
- Connectivity / merge sets
- Time
- α(n) per op
- Edge weights
n/a- Best for
- Dynamic connectivity, Kruskal's cycle check, percolation, image segmentation.
- Solves
- Minimum spanning tree
- Time
- O(E log E)
- Edge weights
Any (no neg cycle issues)- Best for
- Sparse graphs; edges already sorted; when you have a fast DSU.
- Solves
- Minimum spanning tree
- Time
- O((V + E) log V)
- Edge weights
Any- Best for
- Dense graphs; when you have one starting vertex and want to grow outward.
- Solves
- Single goal shortest path
- Time
- O(E) with a good heuristic
- Edge weights
Non-negative + heuristic- Best for
- Pathfinding to a known target — games, GPS, robotics, anywhere geometry hints help.
Decision guide
Which one should you use?
A practical tour of when each algorithm wins.
How to pick
- Unweighted graph, shortest path in edges → BFS. Every edge counts the same, so first-seen is shortest. Don't reach for Dijkstra here.
- Need an order, not a path → DFS if you can recurse; topological sort if you need a linear schedule out of a DAG.
- Weighted graph, positive weights, one source → Dijkstra. The default. Fast, well-understood, every standard library has it.
- Weighted graph with negative edges or a need to detect negative cycles → Bellman-Ford. Slower, but it works where Dijkstra can't.
- You need every pairwise distance, graph is small/dense → Floyd-Warshall. Three nested loops, easy to write, O(V³).
- Cheapest network that connects every node → Kruskal if your graph is sparse (and you have a good DSU), Prim if it's dense.
- *Pathfinder to a known goal with a notion of distance to it → A**. Same answer as Dijkstra, often 10× faster, because the heuristic biases the search toward the goal.
Greedy works for shortest paths — here's why
Dijkstra and Prim are both greedy: at each step they grab the cheapest frontier edge and commit. The reason that works (and isn't just lucky) is the cut property — for any cut of the graph, the cheapest crossing edge belongs to some MST, and the closest unsettled node from a source has its final distance fixed. Bellman-Ford gives this up — it has to relax repeatedly because negative edges break the cut property — and that's exactly where the V×E factor comes from.
Concepts in this track
10 concepts, in order
Each links to a concept page with its own explanation, prototype, and quiz.
Breadth-First Search
Visit a graph in expanding rings from the start — the foundation under shortest paths in unweighted graphs and almost every layered algorithm.
Depth-First Search
Go as deep as you can, then back up. The recursive twin of BFS — the engine behind cycle detection, topological sort, and connected components.
Topological Sort
Order the nodes of a DAG so every edge points forward. The classic build-order, course-prerequisite, and task-scheduling primitive.
Dijkstra's Shortest Path
Single-source shortest paths in a non-negative weighted graph — grow a frontier by always settling the closest unsettled node.
Bellman-Ford
Single-source shortest paths that survive negative edges. Relax every edge n-1 times — slower than Dijkstra, but catches negative cycles.
Floyd-Warshall
All-pairs shortest paths in three nested loops. A dense-matrix DP that's still the right tool when you need every distance.
Union-Find (DSU)
Disjoint sets in near-constant time. The data structure that makes Kruskal's MST, connectivity queries, and Kruskal-like sweeps actually fast.
Kruskal's MST
Sort the edges, add the cheapest one that doesn't form a cycle. Union-Find polices the cycle check in α(n) per edge.
Prim's MST
Grow one tree from a seed node, always pulling in the cheapest edge that reaches a new vertex. Dijkstra's twin for spanning trees.
A* Search
Dijkstra plus a heuristic that whispers 'go this way.' The pathfinder behind game AI, GPS routing, and robotics motion planning.
Related tracks
If this one clicks, try these next.
Sorting
Order a list — ten ways. From the textbook swap-adjacent sorts you write in a single loop, to the divide-and-conquer giants, to the non-comparison tricks that beat O(n log n), to the hybrid your language's sort() actually uses.
Rate Limiting
Control request throughput so a noisy client cannot starve everyone else. Compare the five canonical algorithms side-by-side.
Cache Write Policies
Three ways to handle a write when you have a cache in front of the store. Each policy is a different bet about durability, throughput, and how stale your data is allowed to get.