Graph Complexity Cheatsheet

Everything in one table. $V=n$ vertices, $E=m$ edges.

Traversal and connectivity

Algorithm	Time	Space	Notes
DFS / BFS	$O(V+E)$	$O(V)$	BFS gives unweighted shortest paths
Connected components	$O(V+E)$	$O(V)$	repeated DFS, or DSU
Bipartite check	$O(V+E)$	$O(V)$	2-colouring
Cycle detection	$O(V+E)$	$O(V)$	colours (directed), parent (undirected)
Topological sort	$O(V+E)$	$O(V)$	DAGs only
Bridges / articulation points	$O(V+E)$	$O(V)$	low-link DFS
SCC (Tarjan)	$O(V+E)$	$O(V)$	one DFS
SCC (Kosaraju)	$O(V+E)$	$O(V+E)$	two DFS + transpose
2-SAT	$O(V+E)$	$O(V+E)$	SCC on the implication graph
DSU	$O(\alpha (n))$ amortized	$O(V)$	path compression + union by size
Offline dynamic connectivity	$O((V+Q)\log Q\log V)$	$O(V+Q)$	segment tree on time + rollback DSU

Shortest paths

Algorithm	Time	Negative weights	Notes
BFS	$O(V+E)$	—	unweighted
0-1 BFS	$O(V+E)$	no	weights in $\{0,1\}$, deque
Dial’s algorithm	$O(VC+E)$	no	small integer weights $\le C$
DAG topological DP	$O(V+E)$	yes	DAG only; also gives longest path
Dijkstra (binary heap)	$O(E\log V)$	no	the default
Dijkstra (Fibonacci heap)	$O(E+V\log V)$	no	theory only
Dijkstra (dense, array)	$O(V^2)$	no	better when $E\approx V^2$
Bellman-Ford	$O(VE)$	yes	detects negative cycles
SPFA	$O(VE)$ worst, fast avg	yes	can be hacked
Floyd-Warshall	$O(V^3)$	yes	all pairs, $V\le 500$
Johnson	$O(VE+V^2\log V)$	yes	all pairs, sparse
A*	depends on heuristic	no	needs an admissible heuristic
Yen ($k$ shortest, loopless)	$O(KV(E+V\log V))$	no
Eppstein ($k$ shortest, loops ok)	$O(E+V\log V+K)$	no

Trees and spanning trees

Algorithm	Time	Notes
Tree diameter	$O(V)$	two BFS, or one DFS DP
LCA (binary lifting)	$O(V\log V)$ / $O(\log V)$	also gives $k$-th ancestor
LCA (Euler + sparse table)	$O(V\log V)$ / $O(1)$	best constant
LCA (Tarjan offline)	$O((V+Q)\alpha )$	queries known in advance
Kruskal MST	$O(E\log E)$	needs DSU
Prim MST (heap)	$O(E\log V)$
Prim (dense, array)	$O(V^2)$	better when $E\approx V^2$
Borůvka	$O(E\log V)$	parallelisable
Second-best MST	$O(E\log E+V^2)$	max edge on tree paths
Chu-Liu/Edmonds (arborescence)	$O(VE)$ or $O(E\log V)$	directed MST
HLD + segment tree	$O({\log }^{2}V)$ per query	path queries
Centroid decomposition	$O(V\log V)$ build	path-counting problems
DSU on tree	$O(V\log V)$	subtree aggregate queries

Flows and matching

Algorithm	Time	Notes
Ford-Fulkerson	$O(EF)$	pseudo-polynomial
Edmonds-Karp	$O(V{E}^2)$	BFS augmenting paths
Dinic	$O(V^{2}E)$; $O(E\sqrt{V})$ unit caps	write this
Push-relabel (highest label)	$O(V^2\sqrt{E})$	best for dense graphs
Kuhn (bipartite matching)	$O(VE)$	short and usually enough
Hopcroft-Karp	$O(E\sqrt{V})$
Hungarian (assignment)	$O(V^3)$	min-cost perfect matching, bipartite
Blossom (general matching)	$O(V^3)$	non-bipartite
MCMF (SSP + potentials)	$O(F\cdot E\log V)$
Stoer-Wagner (global min cut)	$O(VE+V^2\log V)$	deterministic

Hard problems

Problem	Best exact	Feasible size
TSP (Held-Karp)	$O(2^V{V}^2)$	$V\le 20$-$22$
Hamiltonian path	$O(2^V{V}^2)$	$V\le 20$-$22$
Max clique (Bron-Kerbosch)	$O(3^{V/3})$	$V\le 100$ with bitsets
Chromatic number	$O(2^{V}V)$	$V\le 20$
Steiner tree (Dreyfus-Wagner)	$O(3^{k}V+2^k{V}^2)$	$k\le 15$ terminals
Vertex cover	$O(1.28^k+kV)$	$k\le 40$ (FPT)

---

Choosing a shortest-path algorithm

1. Unweighted → BFS
2. Weights $\in \{0,1\}$ → 0-1 BFS
3. DAG → topological DP (fastest, handles negatives)
4. Non-negative weights → Dijkstra
5. Negative weights, or you need cycle detection → Bellman-Ford
6. All pairs, $V\le 500$ → Floyd-Warshall
7. All pairs, sparse, $V$ large → Johnson

See also: Modelling Patterns · Complexity Cheatsheet