Graph Algorithms
Graphs look like the largest topic and are mostly four algorithms wearing different clothes. Traversal answers connectivity, ordering and cycles. Shortest path splits by whether edges are weighted and whether weights can be negative. Minimum spanning trees are a greedy pair. Union-Find is the odd one out and is worth learning early because it makes several other problems trivial. The hardest part is usually recognising that a problem is a graph problem at all, since grids, word ladders and dependency lists rarely announce themselves as one.
Where to start, and what comes next
- 01
BFS / DFS
Everything else builds on these. Learn the two orders and what each is good for before touching anything weighted.
- 02
Topological Sort
Ordering with dependencies, in both flavours: Kahn's with in-degrees, and reversed post-order from DFS. Kahn's also detects cycles for free.
- 03
Union Find (DSU)
Worth doing before shortest paths. Connectivity questions collapse to almost nothing with it, and Kruskal depends on it.
- 04
Shortest Path
Dijkstra first, then Bellman-Ford for negative weights, then Floyd-Warshall for all pairs. The order matches how often each appears.
- 05
Minimum Spanning Tree
Kruskal and Prim together, since they solve the same problem from opposite directions and the comparison is the lesson.
If you only have time for three things
- BFS for shortest paths on unweighted graphs, including the multi-source variant that seeds every source before the loop starts.
- Union-Find with both path compression and union by rank, which together give near-constant amortised operations.
- Knowing which shortest-path algorithm the weights demand: BFS if unweighted, Dijkstra if non-negative, Bellman-Ford if negatives are possible.
Say the representation out loud before the algorithm. Adjacency list against matrix is a real decision driven by density, and stating it shows you are thinking about the input rather than reciting a solution. The most common failure in this topic is running Dijkstra on a graph with negative edges: it does not crash, it just returns wrong numbers, so the check has to be yours.
The idea underneath
Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.
Problems that use these patterns
Head to head
Questions people ask
How do I know a problem is a graph problem?
Look for things connected to other things, however it is phrased. A grid is a graph where each cell borders four others. A word ladder is a graph where edges join words one letter apart. Course prerequisites are a directed graph. If you can name nodes and edges, it is one.
Adjacency list or matrix?
A list for sparse graphs, which is nearly all real ones, at O(V + E) space. A matrix for dense graphs or when you need constant-time edge lookups, at O(V squared) space regardless of how few edges exist.
Which cycle detection do I use?
Directed graphs need the three-colour DFS, where an edge to a grey node means a back edge and therefore a cycle. Undirected graphs are simpler: any edge to a visited node that is not the parent closes a cycle, and Union-Find handles it too.