The biggest branch. A graph is just a relation, so almost anything can be modelled as one — the skill is recognising which graph problem you are looking at.
Fundamentals
- Graph Fundamentals and Types
- Representations — adjacency list/matrix, edge list, implicit graphs
- Depth First Search
- Breadth First Search
- Connected Components
- Topological Sort · Kahn’s Algorithm
- Shortest Paths on DAGs
- Cycle Detection
- Bipartite Graphs and Colouring
Shortest Paths
- Shortest Paths Overview
- Dijkstra · Bellman-Ford · Floyd-Warshall · Johnson
- 0-1 BFS · SPFA · Dial’s Algorithm
- Negative Cycles
- A* · Yen (k-shortest) · Eppstein · Suurballe
Connectivity
- Bridges and Articulation Points
- Biconnected Components · Block-Cut Tree
- Strongly Connected Components · Condensation Graph
- Tarjan · Kosaraju · Gabow
- Bridge Tree
- Strong Orientation
- Dynamic Connectivity
- 2-SAT
Trees
- Tree Fundamentals
- Tree Diameter · Tree Center
- Lowest Common Ancestor · Binary Lifting
- Euler Tour
- Tree Isomorphism and Hashing
- Prüfer Code
- HLD · Centroid Decomposition · Virtual Tree
Spanning Trees
- Minimum Spanning Tree
- Kruskal · Prim · Borůvka
- Second-Best MST
- Chu-Liu/Edmonds (arborescence)
- Matrix-Tree Theorem
Flows and Matching
- Maximum Flow · Minimum Cut
- Ford-Fulkerson · Edmonds-Karp · Dinic · Push-Relabel
- Minimum Cost Flow · Circulation with Demands
- Bipartite Matching · Kuhn · Hopcroft-Karp
- General Matching · Blossom
- Hungarian (assignment)
- Global Min Cut · Stoer-Wagner · Karger · Gomory-Hu
Paths and Tours
- Eulerian Path and Circuit · Hierholzer
- Hamiltonian Path
- Travelling Salesman · Held-Karp
- Dominator Tree · Lengauer-Tarjan
Reference
- Graph Complexity Cheatsheet
- Modelling Patterns — how to spot the graph inside a problem