Graphs
Nodes and edges. Most grid, dependency and network questions are graph questions in disguise.
What you actually need to hold in your head
- BFS gives shortest path on unweighted edges
- DFS for connectivity, cycles and ordering
- Dijkstra needs non-negative weights
- Union-Find answers connectivity incrementally
Watch it run
Step through the algorithm before you write it.
Explore in rings of increasing distance. The first time BFS reaches a node, it arrived by a shortest path.
Follow one branch as deep as it goes, then backtrack. Each fresh launch from an unvisited node is one connected component.
Always finalise the closest unfinished node, then relax its outgoing edges. Requires non-negative weights.
Repeatedly take any node with no remaining prerequisites. If you cannot empty the graph, there is a cycle.
Each set keeps one representative. Union links two roots, find walks up to the root and flattens the path behind it.
Sort every edge by weight and take it whenever it joins two different components. Union-Find makes the cycle check cheap.
A grid is a graph where each cell touches its four neighbours. Sink each island as you walk it and count how many walks you start.
Patterns in this topic
The trigger phrases are what you are training yourself to notice.
Explore in rings of increasing distance. The first time BFS reaches a node it does so by a shortest path.
Follow one branch to exhaustion, marking visited nodes, then backtrack. Each launch from an unvisited node is one component.
Repeatedly take nodes with zero remaining prerequisites. If you cannot empty the graph there is a cycle.
Each set has a representative. Union links two roots, find walks to the root with path compression.
Grow a settled set, always expanding the unsettled node with the smallest tentative distance, using a priority queue.
Kruskal sorts edges and adds the cheapest edge that joins two different components. Prim grows one tree using a heap.
Graphs problems
Ordered by sheet phase, so the early ones are the highest signal.