28-Part Curriculum — Complete! + 60 Algorithm Deep Dives
All Articles in This Series
A complete path from discrete-math prerequisites through algorithmic graph theory to structural, extremal, probabilistic, machine-learning, scientific, and research-frontier topics. All 28 parts are now published!
Part 1
Sets, Logic & Proof Techniques
The discrete-math bedrock every graph theorem rests on — sets, relations, functions, quantifiers, and how to actually write a proof.
Read Article →
Part 2
Combinatorics, Probability & Algorithm Complexity
Counting arguments, the pigeonhole principle, probability essentials, and how to measure an algorithm's running time before you ever touch a graph.
Read Article →
Part 3
Linear Algebra & Topology Primer
Vectors, matrices, eigenvalues, and just enough point-set topology to later support planarity, genus, and spectral graph theory.
Read Article →
Part 4
What Is a Graph? Types, Families & Representations
Vertices, edges, degree, graph families, and every major representation — adjacency list/matrix, incidence matrix, and CSR.
Read Article →
Part 5
Graph Traversal I — Breadth-First Search
Why BFS proves bipartiteness, finds connected components, and powers web crawlers — plus multi-source and 0-1 BFS.
Read Article →
Part 6
Graph Traversal II — Depth-First Search
Discovery/finish times, the Parenthesis Theorem, and DFS-powered cycle detection and flood fill.
Read Article →
Part 7
DAGs, Topological Sorting & Critical Path Method
Dependency graphs, topological order, DAG dynamic programming, and scheduling real projects with slack.
Read Article →
Part 8
Cycles, Connectivity & Strongly Connected Components
Weak vs. strong connectivity, SCCs and the condensation DAG, bridges, articulation points, and block-cut trees.
Read Article →
Part 9
Shortest Paths I — Dijkstra & Bellman-Ford
Relaxation, shortest-path trees, optimality conditions, and difference constraints — one framework, every shortest-path algorithm.
Read Article →
Part 10
Shortest Paths II — Floyd-Warshall, Johnson's & A*
All-pairs shortest paths two ways, and the heuristic-guided search behind GPS routing and game AI.
Read Article →
Part 11
Trees & Minimum Spanning Trees
Rooted trees, arborescences, the Matrix-Tree theorem, tree diameter/center, and LCA queries.
Read Article →
Part 12
Eulerian & Hamiltonian Graphs
The Seven Bridges of Königsberg, Euler's 1736 proof, the Chinese Postman Problem, and Hamiltonian cycles.
Read Article →
Part 13
Graph Coloring
The Four Color Theorem's controversial computer-assisted proof, Brooks' theorem, Vizing's theorem, and register allocation.
Read Article →
Part 14
The Traveling Salesman Problem
From an 1832 salesman's handbook to Dantzig's 1954 landmark solution, NP-hardness, and Christofides' approximation.
Read Article →
Part 15
Network Flow & Cuts
The classified 1955 RAND railway study, residual networks, and the Max-Flow Min-Cut Theorem.
Read Article →
Part 16
Matching Theory
Hall's Marriage Theorem, König's duality, Berge's theorem, and medical residency matching.
Read Article →
Part 17
Planar Graphs & Topological Graph Theory
Euler's polyhedron formula, Kuratowski's and Wagner's forbidden-subgraph theorems, and graph genus.
Read Article →
Part 18
Special Graph Families, Isomorphism & Minors
Perfect graphs, the graph isomorphism problem, and the sweeping Robertson-Seymour graph minor theorem.
Read Article →
Part 19
Extremal Graph Theory & Ramsey Theory
Why complete disorder is impossible at scale — Ramsey's theorem, Turán's theorem, and the party problem.
Read Article →
Part 20
Probabilistic, Random & Spectral Graph Theory
The Erdős–Rényi random graph model, the probabilistic method, and what eigenvalues reveal about structure.
Read Article →
Part 21
Infinite Graph Theory
Ends, rays, König's Infinity Lemma, and how graph theory extends gracefully beyond the finite.
Read Article →
Part 22
Complexity, Approximation & Combinatorial Optimization
Cook-Levin, Karp's 21 NP-complete problems, matroid theory, and approximation algorithms.
Read Article →
Part 23
Modern Graph Algorithms — Dynamic, Streaming & Distributed
How graph algorithms scale to data too large for one machine or too fast-changing to store in full.
Read Article →
Part 24
Hypergraphs, Temporal & Multilayer Networks
Modeling group relationships, time-varying connections, and multiple relationship types at once.
Read Article →
Part 25
Network Science
Centrality measures, community detection, small-world networks, and scale-free networks.
Read Article →
Part 26
Graph Machine Learning & Knowledge Graphs
How modern AI learns from graph-structured data — message passing, GNNs, and knowledge graph embeddings.
Read Article →
Part 27
Graph Applications in Science
Cayley's 1874 isomer-counting trees, protein networks, phylogenetics, and percolation theory.
Read Article →
Part 28
Current Research Frontiers & Research Skills
The Hadwiger and Reconstruction conjectures, how to read a paper, and where research happens — the series finale.
Read Article →
60 Algorithm Deep Dives
Algorithm Deep Dives
Standalone reference guides for individual graph algorithms — full derivation, pseudocode, Python/C++/Java implementations, complexity analysis, and worked examples. Organized by topic below, roughly progressing from foundational traversal through classical algorithmic graph theory to advanced structural and machine-learning methods. Read independently of the main parts.
6 Algorithms
Traversal & Ordering Fundamentals
The queue- and stack-driven basics every later algorithm on this page builds on.
Traversal
Breadth-First Search (BFS)
Level-by-level traversal, shortest paths in unweighted graphs, bipartiteness testing, and an interactive step-through demo.
Read Deep Dive →
Traversal
Depth-First Search (DFS)
Recursive and iterative DFS, discovery/finish times, edge classification, and the same interactive demo continued.
Read Deep Dive →
Shortest Path
Multi-Source BFS
Finding shortest distances from any of several sources simultaneously in a single O(V+E) pass.
Read Deep Dive →
Shortest Path
0-1 BFS & Bidirectional Search
Linear-time 0-1 BFS with double-ended queues and exponential search-space reduction via Bidirectional Search.
Read Deep Dive →
Ordering
Kahn's Algorithm (Topological Sort)
A BFS-flavored topological sort from 1962 — the algorithm behind every package manager's install order.
Read Deep Dive →
Topological Sort
DFS-Based Topological Sort
Ordering DAG vertices by reverse postorder of DFS finish times — the original topological sort.
Read Deep Dive →
9 Algorithms
Shortest Paths
Single-source, all-pairs, and specialized-weight shortest-path algorithms, from the classical trio to compact distance oracles.
Shortest Path
Dijkstra's Algorithm
The greedy single-source shortest-path algorithm — correctness proof, binary-heap implementation, and where it fails.
Read Deep Dive →
Shortest Path
Bellman-Ford Algorithm
Shortest paths with negative edge weights, negative-cycle detection, and FOREX arbitrage.
Read Deep Dive →
All-Pairs
Floyd-Warshall Algorithm
All-pairs shortest paths in three nested loops — independently discovered three times between 1959 and 1962.
Read Deep Dive →
Reachability
Warshall's Algorithm (Transitive Closure)
Computing the full reachability matrix of a directed graph via boolean dynamic programming.
Read Deep Dive →
All-Pairs
Johnson's Algorithm
All-pairs shortest paths on sparse graphs with negative edges, via reweighting and Dijkstra.
Read Deep Dive →
Heuristic
A* Search
Built in 1968 for a robot named Shakey — still the default choice for game AI and robot navigation.
Read Deep Dive →
Shortest Path
Dial's Algorithm
Robert B. Dial's 1969 bucket-queue optimization for Dijkstra's algorithm on small integer edge weights.
Read Deep Dive →
Shortest Path
DAG Shortest & Longest Paths
Topological-order relaxation solves both shortest and longest paths, even with negative weights, in O(V+E).
Read Deep Dive →
Distances
Thorup-Zwick Distance Oracles
Trade bounded error for compact, fast distance queries.
Read Deep Dive →
8 Algorithms
Minimum Spanning Trees & Tree Structures
Building, counting, and querying trees — spanning trees, arborescences, spanning-tree counting, and fast tree-query data structures.
MST
Kruskal's Algorithm
Building a minimum spanning tree edge-by-edge with the cut property, cycle property, and Union-Find.
Read Deep Dive →
MST
Prim's Algorithm
Growing a minimum spanning tree one vertex at a time — a 1930 Czech discovery rediscovered twice more.
Read Deep Dive →
MST
Borůvka's Algorithm
The 1926 minimum spanning tree algorithm that predates Kruskal's and Prim's by three decades.
Read Deep Dive →
Data Structure
Union-Find (Disjoint Set Union)
Near-constant-time connectivity queries, path compression, union by rank, and the inverse Ackermann bound.
Read Deep Dive →
Directed MST
Chu-Liu/Edmonds Algorithm
Finding the minimum spanning arborescence of a directed graph by cycle contraction.
Read Deep Dive →
Algebraic
Matrix-Tree Theorem
Count spanning trees with a Laplacian determinant.
Read Deep Dive →
Tree Queries
Lowest Common Ancestor (LCA)
Binary lifting and Euler tour RMQ reduction for querying tree ancestors in O(log N) and O(1) time.
Read Deep Dive →
Tree Decomposition
Heavy-Light Decomposition (HLD)
Decomposing arbitrary trees into disjoint linear paths for O(log² N) path queries and updates.
Read Deep Dive →
5 Algorithms
Connectivity & Strongly Connected Components
Finding single points of failure and strongly connected regions, from static analysis to fully dynamic maintenance.
SCC
Kosaraju's Algorithm
Two DFS passes — one on the graph, one on its transpose — find every strongly connected component.
Read Deep Dive →
SCC
Tarjan's SCC Algorithm
A single DFS pass with low-link values and a stack — no transpose graph required.
Read Deep Dive →
SCC
Gabow's SCC Algorithm
Harold N. Gabow's 1980 two-stack path-based algorithm for finding strongly connected components without low-link values.
Read Deep Dive →
Connectivity
Bridge-Finding & Articulation Points
A single DFS pass with low-link values reveals every single point of failure in a network.
Read Deep Dive →
Dynamic
Dynamic Connectivity
Maintain components while graph edges change.
Read Deep Dive →
7 Algorithms
Network Flow & Cuts
Maximum flow, minimum cost flow, and global minimum cuts — from the original augmenting-path method to randomized contraction.
Max-Flow
Ford-Fulkerson Method
The 1956 RAND report's residual-graph augmenting-path method for computing maximum flow.
Read Deep Dive →
Max-Flow
Edmonds-Karp Algorithm
A Cold War tale of independent discovery — BFS-based augmenting paths guarantee strongly polynomial time.
Read Deep Dive →
Max-Flow
Dinic's Algorithm
The 1970 Soviet breakthrough that finds max flow via level graphs and blocking flows.
Read Deep Dive →
Optimization
Minimum-Cost Maximum Flow
Send maximum flow while minimizing routing cost.
Read Deep Dive →Flow
Circulation with Lower Bounds
Reduce mandatory commitments to a max-flow test.
Read Deep Dive →
Min-Cut
Stoer-Wagner Algorithm
Finds the global minimum cut of a weighted graph via maximum adjacency search — no source, no sink, no flow.
Read Deep Dive →
Min-Cut
Karger's Min-Cut Algorithm
A randomized contraction algorithm that finds the global minimum cut with high probability.
Read Deep Dive →
4 Algorithms
Matching & Assignment
Pairing up vertices optimally — bipartite matching, weighted assignment, general-graph matching, and a matching-powered DAG reduction.
Matching
Hopcroft-Karp Algorithm
Phase-based BFS/DFS layering finds maximum bipartite matchings in O(E√V).
Read Deep Dive →
Assignment
Hungarian Algorithm
Named for two Hungarian mathematicians — finds the minimum-cost perfect assignment in O(n³).
Read Deep Dive →
Matching
Blossom Algorithm
Maximum matching in general (non-bipartite) graphs by contracting odd cycles.
Read Deep Dive →
DAGs
Minimum Path Cover in DAGs
Cover a dependency graph with the fewest disjoint chains.
Read Deep Dive →
4 Algorithms
The Traveling Salesman Problem
Exact, dynamic-programming, and heuristic approaches to the classic NP-hard tour problem.
TSP
TSP: Brute Force, Backtracking & Sorted Edges
Exhaustive permutation search to a fast greedy edge-selection constructive method.
Read Deep Dive →
TSP
Held-Karp Algorithm
Solving TSP exactly via dynamic programming over subsets — exponential, but far faster than brute force.
Read Deep Dive →
Optimization
TSP Heuristics (NN, 2-Opt & 3-Opt)
Nearest Neighbor, 2-Opt, and 3-Opt local search for solving massive Traveling Salesman Problem instances in seconds.
Read Deep Dive →
Approximation
Christofides Algorithm
A polynomial-time 3/2-approximation for metric TSP built from an MST, matching, and Eulerian circuit.
Read Deep Dive →
2 Algorithms
Eulerian & Hamiltonian Graphs
Visiting every edge versus visiting every vertex — one is linear time, the other is NP-complete.
Eulerian
Hierholzer's Algorithm
Published posthumously in 1873 — finds an Eulerian circuit in linear time.
Read Deep Dive →
NP-Complete
Hamiltonian Cycle Backtracking
Exhaustively searching for a cycle visiting every vertex exactly once, with pruning.
Read Deep Dive →
2 Algorithms
Graph Coloring
Linear-time 2-coloring versus NP-complete k-coloring, plus the fast heuristics used when an exact answer isn't required.
Coloring
Bipartite Testing & k-Colorability Backtracking
A linear-time BFS/DFS check for 2 colors versus NP-complete exhaustive search for 3 or more.
Read Deep Dive →
Coloring
Graph Coloring Heuristics
Greedy, Welsh-Powell, and DSatur heuristics for fast, near-optimal graph colorings.
Read Deep Dive →
3 Algorithms
Structural & Sequence Algorithms
Deciding whether a structure is realizable or tractable — degree sequences, planar embeddings, and bounded-treewidth graphs.
Construction
Havel-Hakimi Algorithm
Deciding whether a sequence of numbers can be a graph's degree sequence, and constructing one if so.
Read Deep Dive →
Planarity
Linear-Time Planarity Testing
Find a crossing-free embedding or a forbidden witness.
Read Deep Dive →Structural
Treewidth Dynamic Programming
Solve hard problems through small boundary states.
Read Deep Dive →
3 Algorithms
Spectral & Probabilistic Methods
Eigenvalues, random surfers, and randomized sampling — where linear algebra and probability drive graph algorithms.
Spectral
Spectral Graph Partitioning
Use Laplacian eigenvectors to expose natural cuts.
Read Deep Dive →
Ranking
PageRank
The random-surfer model and power iteration behind the algorithm that ranked the early web.
Read Deep Dive →
Scaling
Graph Sparsification
Retain important structure with far fewer edges.
Read Deep Dive →
3 Algorithms
Community Detection & Network Science
Finding densely-connected groups within a larger network, from betweenness-based splitting to modularity optimization at scale.
Communities
Girvan-Newman Algorithm
Detecting communities by repeatedly removing the network's highest-betweenness bridge edges.
Read Deep Dive →
Communities
Louvain Method
Detecting communities in networks with millions of vertices by greedily optimizing modularity.
Read Deep Dive →
Communities
Leiden Algorithm
Fixing the Louvain method's disconnected-community flaw using fast local refinement and guaranteed connectivity.
Read Deep Dive →
4 Algorithms
Graph Machine Learning
The most advanced deep dives on this page — where isomorphism heuristics became the theoretical ceiling on modern graph neural networks.
Isomorphism
Weisfeiler-Leman Algorithm
A 1968 isomorphism heuristic that became the mathematical ceiling on GNN expressiveness.
Read Deep Dive →
Graph ML
Graph Neural Networks (GCN & GraphSAGE)
Spectral graph convolutions (Kipf & Welling 2017) and inductive neighborhood aggregation (Hamilton et al. 2017).
Read Deep Dive →
Graph ML
Graph Attention Networks (GAT)
Learned, importance-weighted neighbor aggregation using the Transformer's self-attention mechanism.
Read Deep Dive →
Graph ML
Graph Isomorphism Networks (GIN)
The provably maximally-expressive message-passing GNN, matching the 1-WL isomorphism test.
Read Deep Dive →
All 28 main parts are published, and the algorithm deep dive library keeps growing — 60 and counting! Every core algorithm is covered, with advanced methods now added.