Graph
Learning Roadmap
Solid arrows are prerequisites - master the source before the target. Dashed nodes are the stretch tier, worth visiting once the core is solid.
Phase 1 · Foundations
Phase 2 · Core Patterns
Phase 3 · Applied
Graph Anatomyvertices · edges · degree · pathsGraph Representationsadjacency list · matrix · edge listBFSqueue · level by levelDFSrecursion / stack · go deepConnected Componentsflood fill · grids as graphsCycle Detectiondirected vs undirectedTopological SortKahn's · DFS postorderUnion-Find (DSU)path compression · rankShortest PathsBFS unweighted · DijkstraBipartite Check2-coloring via BFSBellman-Fordnegative edges · neg-cycle detectionMSTKruskal · PrimSCCTarjan · KosarajuBridges & Cut Verticeslow-link · single points of failureColoring & Coveringchromatic number · the NP-hard mapFlows & Matchingmax flow · min cut · matchingGrids as Graphsimplicit edges · flood fill · layersTrees as Graphsdiameter · center · LCA · tree DPGraphs in the WildPageRank · centrality · at scaleEulerian & Hamiltonianevery edge · every vertexprerequisite
Learn
- Graph Anatomy - the vocabulary, drawn out: vertices, edges, adjacency vs incidence, degree and the handshake lemma, walks/trails/paths/cycles, simple vs multigraphs, dense vs sparse, and the shape zoo. Start here if any graph word has ever been fuzzy.
- Representation - graph properties, adjacency list/matrix/edge list, building the graph from the input you were given, and the traps that come from mixing representations up. After this: you can pick the right representation and read matrix rows without the index-vs-value bug.
- Traversal - the one BFS/DFS engine, its classic traps, and connected components. This is the page to actually internalize - almost every graph problem is this engine with one knob turned.
- Cycles & Ordering - cycle detection (directed and undirected), topological sort, union-find. Builds directly on Traversal's DFS.
- Shortest Paths & Bipartite Check - Dijkstra, Bellman-Ford, and 2-coloring via BFS. What BFS becomes once edges stop costing the same.
- MST, SCC & Connectivity - Kruskal, Prim, Tarjan, Kosaraju, bridges, articulation points, condensation. Everything about a graph's connective structure: cheapest way to connect it, which vertices can all reach each other, and which single edge or vertex would break it.
- Eulerian & Hamiltonian - every-edge-once vs every-vertex-once, degree conditions, Hierholzer, and why one is linear and the other NP-complete. Read it for the asymmetry alone.
- Coloring & Covering - the chromatic number, greedy coloring, independent sets, cliques, vertex covers, and the NP-hard map. Where the cliff between 2 colors and 3 colors actually is.
- Flows & Matching - max flow, min cut, bipartite matching, Konig and Hall, and the reduction table. The polynomial half of the hard problems - read section 4 even if you skip the rest.
- Grids as Graphs - the implicit edges of a 2D grid,
DIRS4vsDIRS8, the four ways to trackvisited, flood fill, the border-seeded inversion, and layered grids. The most common graph problem is the one that never says "graph". - Trees as Graphs - a tree given as an edge list: rooting it, diameter by double sweep, center vs centroid, LCA by binary lifting, tree DP and rerooting. What to do when there is no
.leftand.right. - Graphs in the Wild - which production system runs which algorithm, centrality and PageRank, what changes when the graph does not fit in memory, and graph databases. Not needed for interviews; read it to make the rest stick.
What do I reach for
The whole section compressed into one lookup. Read the question, not the graph: the phrasing decides the algorithm far more often than the input shape does.
| The question asks for | Reach for | Cost |
|---|---|---|
| "is there a path", "are these connected", "how many groups" | DFS or BFS, or union-find if edges arrive one at a time | O(V + E) |
| "fewest steps", "minimum moves", unweighted | BFS - Traversal | O(V + E) |
| "distance to the nearest of several starts" | multi-source BFS - seed every source at distance 0 | O(V + E) |
| "cheapest route", non-negative weights | Dijkstra - Shortest Paths | O((V + E) log V) |
| "cheapest route", some weight is negative | Bellman-Ford, and it detects negative cycles too | O(V * E) |
| "cheapest route between every pair" | Floyd-Warshall, if V is small or the graph is dense | O(V^3) |
| "is this schedulable", "what order", "does it deadlock" | topological sort - Cycles & Ordering | O(V + E) |
| "how many rounds/semesters/stages" | Kahn's, drained one generation at a time | O(V + E) |
| "cheapest way to connect everything" | Kruskal or Prim - MST | O(E log E) |
| "which groups can all reach each other" | Tarjan or Kosaraju, then condense to a DAG | O(V + E) |
| "which single link/machine is critical" | bridges and articulation points - low-link | O(V + E) |
| "split into two groups with no conflict inside" | 2-coloring BFS - bipartite check | O(V + E) |
| "use every edge exactly once" | degree parity, then Hierholzer - Eulerian | O(V + E) |
"visit every vertex exactly once", n <= 20 | bitmask DP - Hamiltonian | O(2^n * n^2) |
| "assign each of these to one of those" | bipartite matching - Flows & Matching | polynomial |
| "what is the bottleneck", "cheapest set of links to cut" | max flow / min cut | polynomial |
| "largest conflict-free set", "fewest to cover everything" | independent set / vertex cover - NP-hard unless bipartite, a tree, or n is small (Coloring & Covering) | see the NP-hard map |
| it is a grid and asks about regions, distances, or reachability | BFS or DFS with a direction-offset neighbour function - Grids as Graphs | O(R * C) |
it is a tree (edge list, n - 1 edges) and asks for the longest path | double-sweep BFS for the diameter - Trees as Graphs | O(V) |
| "which root minimises the height", "the middle of the tree" | peel leaves layer by layer to find the center | O(V) |
| repeated "distance between these two tree vertices" | LCA by binary lifting | O(V log V) prep, O(log V) per query |
| the answer for every vertex as root | rerooting: one down pass, one up pass | O(V) |
"cheapest subject to at most k X" | state-augmented Dijkstra over (node, k) - Dijkstra variants | O(E k log(V k)) |
| "minimise the largest single step" | Dijkstra with max relaxation, or binary search + BFS | O((V + E) log V) |
| pick true/false per variable, constraints over pairs | 2-SAT via the implication graph and SCCs - 2-SAT | O(V + E) |
| tasks with durations: "how long, and which tasks are tight" | critical path method - forward pass, backward pass, slack | O(V + E) |
| "which of these is most important/influential" | centrality or PageRank - Graphs in the Wild | varies |
The bug checklist
Every trap on the learn pages, compressed into the order they tend to bite. If a graph solution is wrong and you do not know why, read down this list.
| # | Check | Symptom when wrong |
|---|---|---|
| 1 | Did you append both directions for an undirected edge? | Components over-counted; paths reported missing. |
| 2 | Does [a, b] point the way you think? For prerequisites the edge runs b -> a. | Order comes out reversed. Note the boolean version of the problem still passes. |
| 3 | Are isolated vertices in the adjacency structure, or did you build only from edges? | Component count too low; len(adj) != n. |
| 4 | Is visited marked on enqueue/push, not on dequeue/pop? | Duplicates flood the queue; recursive DFS overflows. |
| 5 | Does the visited key include every part of the state - (r, c, keys), (node, stops)? | A valid route is rejected; answer too high or -1. |
| 6 | Is the outer for v in graph: if v not in visited loop present? | Only one component is ever processed. |
| 7 | Directed cycle detection: 3 colours and no parent-skip. Undirected: parent-skip is required. | False negatives on 2-cycles, or false positives on a plain DAG. |
| 8 | Bounds checked before indexing a grid cell? | Python negative indexing wraps silently - no error, wrong answer. |
| 9 | Kahn: is the cycle test len(order) == n, not "the pool started empty"? | Cycles that leave the pool non-empty at the start are missed. |
| 10 | Postorder built and then reversed? (topological sort, Hierholzer, Kosaraju) | The answer is exactly backwards. |
| 11 | Dijkstra: is every weight non-negative? Prim: is the heap key the raw edge weight, not a running total? | Silently wrong optimum; Prim builds a shortest-path tree instead of an MST. |
| 12 | Floyd-Warshall: is k the outermost loop? | Distances too large; passes on small inputs. |
| 13 | Bridges use low[v] > disc[u]; articulation points use >= plus the root rule. | Correct on trees, wrong on everything with a cycle. |
| 14 | Union-find: size[winner] += size[loser], and compression writes to the caller's entry. | Off-by-a-few sizes; compression silently does nothing. |
| 15 | Was parent[v] = u set inside the same if as the distance update? | Correct distances, nonsense reconstructed path. |
| 16 | Recursion depth: could this input exceed about 1000 frames? | RecursionError on large but legal input. |
Practice
- Traversal - BFS/DFS problems.
- Cycle Detection - directed and undirected cycle problems.
- Topological Sorting - Kahn's and DFS-postorder problems.
- Degree - degree-counting problems.
- Matrix - grid traversal problems (the islands family, multi-source BFS).