Table of Contents
This cheat sheet is built for two moments: the last hour before a technical interview, and the middle of a coding session when you know the shape of the problem but need the exact tool. It is deliberately compact. For the full story behind each algorithm, follow the links to the deep-dive articles, and if you want a structured path through all of it, start with the graph theory study roadmap.
Throughout, V is the number of vertices (nodes) and E is the number of edges.
The Master Complexity Table
The single most useful thing to have memorized. Complexities assume the standard efficient implementation (binary heap for Dijkstra and Prim, path compression and union by rank for union-find).
| Algorithm | Best for | Time | Space |
|---|---|---|---|
| BFS | Shortest path in unweighted graphs, level order | O(V + E) | O(V) |
| DFS | Connectivity, cycles, exploring structure | O(V + E) | O(V) |
| Dijkstra | Shortest path, non-negative weights | O((V + E) log V) | O(V) |
| Bellman-Ford | Shortest path with negative weights | O(V · E) | O(V) |
| Floyd-Warshall | All-pairs shortest paths, small dense graphs | O(V³) | O(V²) |
| A* | Heuristic shortest path (maps, games) | O(E) typical | O(V) |
| Kruskal | Minimum spanning tree, sparse graphs | O(E log E) | O(V) |
| Prim | Minimum spanning tree, dense graphs | O((V + E) log V) | O(V) |
| Topological Sort | Ordering a DAG by dependencies | O(V + E) | O(V) |
| Union-Find | Dynamic connectivity, grouping | O(α(V)) per op | O(V) |
| Tarjan / Kosaraju | Strongly connected components | O(V + E) | O(V) |
| Edmonds-Karp | Maximum flow, minimum cut | O(V · E²) | O(V + E) |
| Need the actual code? This table lists 12 essentials at a glance. The Algorithms Handbook has all 55, each with the pseudocode and its complexity worked out step by step. | |||
Note on A*: its running time depends entirely on the heuristic. With a perfect heuristic it walks almost straight to the goal; with a useless one it degrades to Dijkstra. The α in union-find is the inverse Ackermann function, effectively a small constant for any input you will ever see. For the reasoning behind every row, see the graph algorithms complexity guide.
Graph Representations
Before any algorithm, you choose how to store the graph. This one decision affects every complexity above.
| Representation | Space | Edge lookup | Best for |
|---|---|---|---|
| Adjacency List | O(V + E) | O(degree) | Sparse graphs, the default choice |
| Adjacency Matrix | O(V²) | O(1) | Dense graphs, constant-time lookups |
Rule of thumb: reach for the adjacency list unless the graph is dense or you need constant-time edge checks. A 2D grid is an implicit graph where each cell is a node connected to its neighbours, so you often need no explicit representation at all.
Traversal: BFS and DFS
The two algorithms everything else is built on. Learn the full comparison in BFS vs DFS.
- BFS uses a queue, explores level by level, and finds the shortest path in an unweighted graph. Keywords: shortest, minimum steps, nearest, level order.
- DFS uses a stack (often the recursion call stack), plunges deep, and is ideal for connectivity, cycle detection, and backtracking. Keywords: all paths, reachability, regions, explore.
Shortest Paths
The most common family in interviews and in practice. The right choice is dictated by the edge weights. The full deep dive is in understanding shortest path algorithms.
| Situation | Use | Why |
|---|---|---|
| Unweighted edges | BFS | First arrival is the shortest path |
| Non-negative weights | Dijkstra | Greedy with a min-heap, always correct here |
| Negative weights | Bellman-Ford | Relaxes edges V-1 times, detects negative cycles |
| All pairs at once | Floyd-Warshall | Three nested loops, tiny code, great on small graphs |
| You have a heuristic | A* | Dijkstra guided toward the goal, see A* |
The classic trap: never run Dijkstra on a graph with negative edges. It commits to a node as final too early and can return a wrong answer. Reach for Bellman-Ford instead.
Minimum Spanning Trees
Connect every vertex at the lowest total edge cost. Both algorithms are correct; pick by graph density. Full walk-throughs in minimum spanning trees.
- Kruskal: sort all edges, add the cheapest that does not form a cycle, using union-find to test for cycles. Shines on sparse graphs.
- Prim: grow a single tree outward, always adding the cheapest edge leaving it, using a priority queue. Shines on dense graphs.
Ordering and Connectivity
- Topological Sort (Kahn's or DFS-based): produces a linear order of a DAG so every edge points forward. The tool for dependencies, build order, and scheduling. Impossible if a cycle exists, which is exactly how you detect one.
- Union-Find (Disjoint Set): answers "are these two in the same group?" and merges groups in near-constant time. The backbone of Kruskal and of dynamic-connectivity problems.
- Strongly Connected Components (Tarjan or Kosaraju): finds maximal groups where every node reaches every other, in a directed graph. Both run in
O(V + E).
All three appear constantly in interviews. See the worked patterns in essential graph algorithms for coding interviews.
Network Flow
Model throughput, matching, and bottlenecks. The elegant result here is that the maximum flow equals the minimum cut. Full treatment in network flow and the max-flow min-cut theorem.
- Ford-Fulkerson: repeatedly push flow along augmenting paths in the residual graph. Simple, but its running time depends on the flow values.
- Edmonds-Karp: Ford-Fulkerson that finds augmenting paths with BFS, giving a clean
O(V · E²)bound independent of the capacities.
Which Algorithm Should I Use?
The fastest way to use this cheat sheet: read the left column, jump to the right.
| If you need to… | Reach for |
|---|---|
| Visit or explore every node | BFS or DFS |
| Find the shortest path in an unweighted graph | BFS |
| Find the shortest path with non-negative weights | Dijkstra |
| Handle negative edge weights | Bellman-Ford |
| Get shortest paths between all pairs | Floyd-Warshall |
| Find a fast path with a heuristic (maps, games) | A* |
| Connect everything at minimum cost | Kruskal or Prim |
| Order tasks by their dependencies | Topological Sort |
| Check if two nodes are connected, or group items | Union-Find |
| Find clusters in a directed graph | Tarjan or Kosaraju (SCC) |
| Maximise throughput or find a bottleneck | Edmonds-Karp (max-flow) |
Turn the table into intuition
A cheat sheet tells you which algorithm; watching it run tells you why. Step through any of these on a live graph.
Open the Algorithm VisualizerFrequently Asked Questions
What is the time complexity of Dijkstra's algorithm?
With a binary heap (priority queue), Dijkstra's algorithm runs in O((V + E) log V) time and O(V) space. With a simple array instead of a heap it is O(V squared), which can be faster on dense graphs.
Which graph algorithm should I use for shortest paths?
It depends on the graph. Use BFS for unweighted graphs, Dijkstra for non-negative weights, Bellman-Ford when there are negative weights, Floyd-Warshall for all-pairs shortest paths, and A* when you have a good heuristic (maps and games).
Should I use an adjacency list or an adjacency matrix?
Use an adjacency list for sparse graphs: it uses O(V + E) space and is the default for most problems. Use an adjacency matrix for dense graphs or when you need O(1) edge lookups, at the cost of O(V squared) space.
Which graph algorithms should I memorize for coding interviews?
The core five are BFS, DFS, Dijkstra's algorithm, topological sort, and union-find. Together they cover the large majority of graph questions asked in technical interviews.