Graph algorithms, step by step

how it works

1. Set dist[start] = 0 and every other dist to −1 (not discovered yet). Push start into a queue.
2. Take the node u at the front of the queue.
3. For each neighbor v of u: if it is already discovered, skip it. Otherwise set dist[v] = dist[u] + 1, remember parent[v] = u, and push v to the back.
4. Repeat until the queue is empty. dist[v] is now the fewest edges from start to v; following parent[] back from v and reversing gives the path itself.

why it works

The queue only ever holds two neighboring rings: nodes at distance d at the front, nodes at d + 1 behind them. So nodes leave it in order of distance. Now say v is discovered from u, at distance d. If v had a shorter path, the node just before v on it would be closer than d, would have left the queue before u, and would have discovered v first. So d + 1 is the true distance.

cost

Each node is pushed and popped once, and each edge is looked at once from each end: O(V + E) time. The queue, dist and parent take O(V) memory.

watch out

• Mark a node when you push it, not when you pop it. Marking on pop lets the same node into the queue many times — on a big grid, that is the difference between passing and timing out.
• BFS counts edges. With weighted edges use Dijkstra. With weights of only 0 and 1, use 0-1 BFS: a deque where 0-weight neighbors go to the front.
• A grid is a graph: the neighbors of cell (r, c) are the four cells around it. Check bounds instead of building an adjacency list.
• Several starting points — every rotten orange, every exit? Push them all with distance 0 before the loop. That is multi-source BFS, still O(V + E).
• Need the answer level by level? Read q.size() at the top of each round and pop exactly that many.

practice

• 102Binary Tree Level Order Traversal — one ring at a time
• 200Number of Islands — BFS or DFS flood fill
• 994Rotting Oranges — multi-source
• 1091Shortest Path in Binary Matrix — grid, 8 directions
• 127Word Ladder — the graph is implicit
• 785Is Graph Bipartite? — BFS 2-coloring
• 847Shortest Path Visiting All Nodes — BFS over (node, visited-mask)

how it works

1. Call dfs(start). Each call marks its node visited and records it.
2. Go through the node's neighbors in order. At the first unvisited one, call dfs on it — the current call pauses on the stack and waits.
3. When a node has no unvisited neighbors left, its call returns. The paused caller resumes with its next neighbor: that is backtracking.
4. When dfs(start) returns, everything reachable from the start is visited. For a disconnected graph, start a new dfs from every node that is still unvisited — each new start is one connected component, which is exactly what main() does.

why it works

A node is marked before its neighbors are explored, so no node is entered twice and the recursion ends. A call returns only after all its neighbors are visited, so nothing reachable is missed. The edges DFS walks down (green) form a spanning tree of the component. In an undirected graph, every other edge joins a node to one of its ancestors — which is why meeting a visited node that is not your parent means a cycle.

cost

O(V + E) time, like BFS. The O(V) memory is call stack, though: a path-shaped graph with 10⁵ nodes recurses 10⁵ calls deep, which can overflow the default stack (8 MB on Linux, 1 MB on Windows). For inputs that big, use the version below.

without recursion

An explicit stack where each entry remembers how far through its neighbor list it got gives exactly the recursive order. The popular shortcut — push all neighbors at once — also visits everything, but in a different order.

watch out

• Directed graphs need three states for cycle detection: new, on the current path, finished. Reaching a node on the current path is a cycle; reaching a finished one is not. With only visited and unvisited you get false alarms. The topological sort tab has the three-state version.
• Cycle check in an undirected graph: ignore the edge back to your parent; any other visited neighbor closes a cycle.
• Backtracking problems — permutations, N-Queens, word search — are DFS over partial solutions: mark a choice on the way in, unmark it on the way out.
• DFS paths are not shortest paths. If the question says “minimum steps”, reach for BFS.

practice

• 695Max Area of Island — flood fill, count as you go
• 547Number of Provinces — count components
• 133Clone Graph — visited map doubles as the copy
• 417Pacific Atlantic Water Flow — DFS inward from the borders
• 79Word Search — backtracking
• 207Course Schedule — three-state cycle detection
• 1192Critical Connections in a Network — DFS with low-link values

how it works

1. Count each node's in-degree: how many edges point into it, which is how many prerequisites it still waits for.
2. Queue every node with in-degree 0. Nothing blocks them, so they can go first.
3. Pop a node and append it to the order. Remove its outgoing edges by decrementing each target's in-degree; a target that drops to 0 has all its prerequisites placed, so it joins the queue.
4. When the queue runs dry, count. All nodes placed: the order is valid. Some left over: they still wait on each other, so the graph has a cycle and no order exists. Press add edge 4 → 5 above to watch that happen.

why it works

A node joins the order only after every edge into it is removed, and an edge is removed only when its source is placed — so every edge points from an earlier node to a later one. And the queue cannot run dry too early: a DAG always has a node with in-degree 0 among the ones left (walk edges backwards from any node; without a cycle you have to stop somewhere).

what the order buys you

DP on a DAG. Process nodes in topological order and every node's predecessors are finished before it, so longest path, number of paths and earliest start times all take O(V + E). Longest path is NP-hard in a general graph and linear in a DAG for exactly this reason.

the DFS version

On this graph it returns 6 3 5 2 7 0 1 4 — different from Kahn's 3 6 0 2 5 1 7 4 and just as valid. Topological orders are rarely unique.

watch out

• Get the direction right: “a requires b” is the edge b → a. Flip it and the order comes out reversed.
• Never skip the order.size() < n check. Returning a partial order for a graph with a cycle is the classic Course Schedule bug.
• Need the smallest order lexicographically? Use a min-heap instead of the queue.
• Is the order unique? Only if the queue never holds two nodes at once (LeetCode 444).

practice

• 207Course Schedule — is there a cycle?
• 210Course Schedule II — return the order
• 802Find Eventual Safe States — Kahn on the reversed graph
• 2115Find All Possible Recipes from Given Supplies
• 329Longest Increasing Path in a Matrix — a DAG hiding in a grid
• 269Alien Dictionarypremium — build the DAG first
• 1136Parallel Coursespremium — longest path = semesters

how it works

1. Sort all edges by weight.
2. Put every node in a set of its own: union-find with parent[v] = v.
3. For each edge u–v, lightest first: if find(u) == find(v) the ends are already connected and the edge would close a cycle, so skip it. Otherwise add it to the tree and unite the two sets.
4. Stop at n − 1 edges. If the edges run out first, the graph is disconnected and you have a minimum spanning forest.

why greedy is safe

The cut property: split the nodes into any two groups, and the lightest edge crossing between them belongs to some MST. If a tree avoided it, adding it would make a cycle that crosses the split a second time, on an edge at least as heavy — swap the two and the tree gets no heavier. When Kruskal accepts u–v, every lighter edge has been looked at and none of them crossed from u's set to the rest of the graph (it would have merged them). So u–v is the lightest edge across that split.

union-find

Two small tricks make find nearly free. Union by size hangs the smaller tree under the larger, so trees stay shallow. Path halving makes every node on the way up skip a level. Together a find costs O(α(n)) amortized, where α — the inverse Ackermann function — is at most 4 for any input that fits in a computer. Watch parent[] at the edge 4–6: find(4) re-points parent[4] from 3 straight to 0. The union-find tab shows the structure on its own.

cost

Sorting dominates: O(E log E). All the union-find work together is O(E · α(V)).

watch out

• An MST is not a shortest-path tree. It minimizes the total weight, not the distance from any one node. The Dijkstra tab uses this same graph: its tree takes 2–3 and 2–5 where the MST takes 1–3 and 3–5.
• Negative weights are fine for an MST. For a maximum spanning tree, sort heaviest first.
• When every pair of nodes is connected, E ≈ V² and sorting all of them is wasteful; the heap-free O(V²) Prim wins.
• Union-find is useful on its own: counting components as edges arrive, finding the edge that first closes a cycle, merging accounts that share an email.

practice

• 1584Min Cost to Connect All Points — MST on a complete graph
• 684Redundant Connection — union-find alone
• 721Accounts Merge — union-find on strings
• 1489Find Critical and Pseudo-Critical Edges in MST — rerun with an edge forced in or out
• 1135Connecting Cities With Minimum Costpremium — plain Kruskal
• 1168Optimize Water Distribution in a Villagepremium — a well is an edge to a virtual node

how it works

1. Push {0, start} into a min-heap: reaching the start costs nothing.
2. Pop the cheapest entry {w, v, from}. If v is already in the tree, the entry is stale — skip it.
3. Otherwise v joins the tree through the edge from–v, and w goes into the total.
4. Push every edge from v to a node not in the tree yet.
5. Repeat until the heap is empty. Every node joined exactly once, through n − 1 edges.

why it works

The tree's nodes and all the others form a cut, and Prim always takes the lightest edge crossing it — the same cut property that makes Kruskal correct.

lazy or eager

This version is lazy: it never deletes outdated entries, it skips them when they reach the top (struck through in the heap view). The code stays short and costs O(E log E) = O(E log V). The eager version keeps one entry per node and lowers it with decrease-key, which needs an indexed heap — rarely worth it in an interview.

dense graphs

When every pair of nodes is an edge, E ≈ V² and the heap only adds overhead. Scanning an array for the closest outside node is O(V²) in total — the standard answer to “connect all points”.

kruskal vs prim

Same tree, weight 26. Reach for Kruskal when you are given a list of edges, for Prim when you have adjacency lists or a dense graph.

watch out

• The same node can sit in the heap several times. Check inTree when you pop, not only when you push.
• Prim and Dijkstra look almost identical, but the heap key differs: Prim uses the single edge weight w, Dijkstra the whole path dist[u] + w. Swapping them is a common bug.
• On a disconnected graph Prim only spans the start's component.

practice

• 1584Min Cost to Connect All Points — the O(V²) version
• 778Swim in Rising Water — always expand the lowest frontier cell
• 1135Connecting Cities With Minimum Costpremium
• 1168Optimize Water Distribution in a Villagepremium

how it works

1. dist[source] = 0, every other dist = ∞. Push {0, source} into a min-heap.
2. Pop the smallest entry {d, u}. If d > dist[u] it is stale — u was reached more cheaply after this entry went in — so skip it.
3. Otherwise u is settled: dist[u] is final.
4. Relax each edge u → v with weight w: if dist[u] + w < dist[v], set dist[v] = dist[u] + w, parent[v] = u, and push {dist[v], v}.
5. Repeat until the heap is empty. The parent edges form the shortest-path tree.

why it works

When u is popped with distance d, every unsettled node has a tentative distance of at least d. Any other route to u has to leave the settled region through one of those nodes, so it already costs at least d before its remaining edges — and with no negative weights, those can only add. That last step is exactly what a negative edge breaks.

watch it happen

Node 1 first gets distance 4, straight from 0, then 3 through node 2. The old entry (4, 1) stays in the heap and is skipped when it surfaces. Node 4 goes from 12 to 10 the same way. The C++ needs no “settled” array: the stale check does that job.

cost

Every successful relaxation pushes one entry, so the heap holds at most E of them: O((V + E) log V) time, O(V + E) memory.

watch out

• Negative weights break the proof: a node can be popped before a cheaper route through a negative edge shows up. Use Bellman–Ford, O(V · E), which also detects negative cycles. On a DAG, relaxing edges in topological order works with any weights in O(V + E).
• All weights equal? Plain BFS. Only 0 and 1? 0-1 BFS with a deque. Both are O(V + E).
• Keep distances in long long and never add to ∞: LLONG_MAX + w overflows.
• Many problems hide the graph in a state: (cell, keys held), (city, stops used). Run Dijkstra on the states. With a cap on stops (LeetCode 787), a cheaper route that used more stops can be a dead end, so the state must include the stops.

practice

• 743Network Delay Time — textbook Dijkstra
• 1631Path With Minimum Effort — path cost is a max, not a sum
• 1514Path with Maximum Probability — max-heap, multiply
• 787Cheapest Flights Within K Stops — state = (city, stops)
• 1976Number of Ways to Arrive at Destination — count while relaxing
• 2290Minimum Obstacle Removal to Reach Corner — 0-1 BFS

how it works

1. Push the start with g = 0 and f = h(start).
2. Pop the entry with the smallest f — on ties, the smaller h, the cell that believes it is closer. If its g is worse than the best known for that cell, it is stale: skip it.
3. If it is the goal, stop: its g is the answer. Otherwise look at the neighbors. A neighbor whose cost through this cell, g + 1, beats its best known g takes that g, remembers where it came from, and goes into the heap with f = g + 1 + h.
4. Follow from[] back from the goal for the path. If the heap runs dry first, the goal is unreachable.

why it works

Manhattan distance never overestimates on a four-direction grid — every move changes the row or the column by one — and it is consistent: one move changes h by at most 1, the cost of that move. With a consistent h, A* is exactly Dijkstra run on adjusted weights w + h(v) − h(u), which are never negative. So the Dijkstra argument carries over: once the goal is popped, nothing left in the heap can beat it.

choosing h

• Four directions, each move costs 1: Manhattan, |Δr| + |Δc|.
• Eight directions, each move costs 1: Chebyshev, max(|Δr|, |Δc|).
• Diagonals cost √2: octile distance. Any angle: straight-line distance.
• Sliding-tile puzzles: the sum of every tile's Manhattan distance to its home.
• h = 0 is always safe and gives Dijkstra. An h that overestimates — say f = g + 1.5 · h — finds a path faster, but not always the shortest.

cost

In the worst case it is Dijkstra: O(E log V). In practice a good h expands far fewer cells — 30 instead of 135 on this map. Draw a cup-shaped wall around S and the gap shrinks: h points straight into the cup, and A* has to fill it before it finds the way around.

watch out

• Stop when the goal is popped, not when it is first pushed. The first route to reach it is not always the shortest.
• An h that overestimates breaks the guarantee. Check it against the real move costs: with diagonal moves, Manhattan overestimates.
• Tie-breaking changes speed, not correctness: preferring the smaller h among equal f keeps A* from fanning out across a whole plateau of equal-f cells.
• Many “fewest moves” problems carry extra state — keys collected, walls you may still break. Then a node is (cell, state); h can still look at the cell alone.
• In an interview, BFS on a grid usually suffices. A* is the strong answer to the follow-up: “the grid is huge and you need one path”.

practice

• 1091Shortest Path in Binary Matrix — 8 directions, Chebyshev h
• 773Sliding Puzzle — states are whole boards
• 1293Shortest Path in a Grid with Obstacles Elimination — state = (cell, breaks left)
• 864Shortest Path to Get All Keys — state = (cell, keys held)
• 675Cut Off Trees for Golf Event — many point-to-point searches
• 1197Minimum Knight Movespremium — A* or two-sided BFS

how it works

1. dist[source] = 0, everything else ∞.
2. Repeat V − 1 times: go through every edge u → v and relax it — if dist[u] + w < dist[v], lower dist[v].
3. If a whole round changes nothing, stop early: nothing ever will.
4. Then make one extra pass. If any edge still relaxes, a negative cycle is reachable and shortest distances do not exist. Press add 4 → 1 (−6) above to see it.

why it works

By induction on the number of edges: after round k, dist[v] is at most the cost of the best path to v with at most k edges, because that path's last edge u → v is relaxed in round k, after dist[u] became right in round k − 1. Without negative cycles some shortest path repeats no node, so V − 1 edges are enough. With a negative cycle, going around once more always lowers something, so the extra pass notices.

why not Dijkstra

Dijkstra's proof assumes that once a node is the cheapest in the heap, no later route can beat it, and a negative edge breaks exactly that. A version with a visited array returns wrong distances. The lazy version on the Dijkstra tab re-processes a node whenever its distance drops, so it stays correct, but on bad inputs that can take exponential time.

at most k edges

Cheapest flights with at most k stops: run exactly k + 1 rounds, and relax from a copy of the previous round so one round cannot chain several flights.

cost

V − 1 rounds over E edges: O(V · E) time, O(V) memory. Fine for a few thousand edges, and much slower than Dijkstra when every weight is non-negative.

watch out

• Skip edges out of ∞ — if (dist[u] == INF) continue; — because ∞ plus a negative weight looks like a real distance. Use long long.
• A negative cycle that cannot be reached from the source is invisible. To find any negative cycle at all, start with every dist at 0, as if a virtual source pointed at every node.
• Currency arbitrage is the classic disguise: weight each exchange as −log(rate), and a negative cycle is a loop of trades that makes money.
• SPFA — a queue that only re-relaxes edges out of nodes whose distance just dropped — is often faster in practice, with the same worst case.

practice

• 787Cheapest Flights Within K Stops — k + 1 rounds, relax from a copy
• 743Network Delay Time — works here too, slower than Dijkstra
• 1334Find the City With the Smallest Number of Neighbors at a Threshold Distance — one run per city, or Floyd

how it works

1. d[i][j] = weight of the edge i → j, 0 on the diagonal, ∞ everywhere else.
2. For each k from 0 to V − 1 — the outermost loop — and every pair (i, j): if d[i][k] + d[k][j] < d[i][j], take the route through k.
3. After the last k, d[i][j] is the shortest distance from i to j. A negative d[i][i] means a negative cycle through i.

why it works

A shortest path whose stops all lie in 0 … k either avoids k — then round k − 1 already found it — or passes k exactly once, splitting into i → k and k → j, both with stops below k only. Those two cases are exactly what the inner line compares. Updating in place is safe because row k and column k cannot change during round k: d[i][k] + d[k][k] = d[i][k] when d[k][k] = 0.

cost

V³ checks whatever the edges: 125 for these 5 nodes, 6.4 · 10⁷ for 400 — fine in C++. Past about 500 nodes with non-negative weights, run Dijkstra from every node instead, O(V · E log V).

watch out

• k must be the outermost loop. Put it inside and some distances come out too large — a very common slip.
• Skip ∞ entries before adding. ∞ plus a negative weight is not a path, and ∞ + ∞ overflows unless ∞ is something like LLONG_MAX / 4.
• Negative edges are fine; check the diagonal for negative cycles.
• The same loop with booleans is reachability: reach[i][j] |= reach[i][k] && reach[k][j]. That is Course Schedule IV.
• The tell in a problem statement: few nodes (a few hundred at most) and many “distance between a and b” questions.

practice

• 1334Find the City With the Smallest Number of Neighbors at a Threshold Distance
• 1462Course Schedule IV — reachability for every pair
• 399Evaluate Division — multiply ratios instead of adding
• 2976Minimum Cost to Convert String I — Floyd over 26 letters

how it works

1. Start with parent[v] = v: every node is a root, a group of its own.
2. find(x): follow parent pointers to the root. On the way, path halving points each node at its grandparent, so later climbs are shorter.
3. unite(a, b): find both roots. The same root means one group already — as an edge, it would close a cycle. Different roots: hang the smaller tree under the larger and add up the sizes.
4. “Are a and b connected?” is just find(a) == find(b).

why it is fast

With union by size, a node only moves one level deeper when its tree at least doubles, so no tree gets taller than log₂ n. Path halving then flattens the paths you actually use. Together, m operations cost O(m · α(n)), where α — the inverse Ackermann function — is at most 4 for any n you will ever meet. In the demo, after unite(3, 6) node 3 points straight at 0, and the final query re-points 7 at 4.

cost

Two int arrays, O(n) memory, and each operation is amortized O(α(n)) — call it constant.

watch out

• It cannot split a group. If edges get deleted, run the operations backwards so deletions become merges, or reach for another structure.
• Without union by size or path compression it still passes small tests, then times out on one long chain.
• Counting groups: start at n and subtract one for every unite that returns true.
• Grids: name cell (r, c) as r * cols + c. When land appears one cell at a time, unite each new cell with its land neighbors.
• Extra data can live at the root — a size, a minimum, a ratio to the parent. Weighted union-find solves Evaluate Division.
• Kruskal is union-find plus sorting: the edge that would merge a group with itself is exactly the one that closes a cycle.

practice

• 547Number of Provinces — count the groups
• 684Redundant Connection — the first edge that closes a cycle
• 721Accounts Merge
• 990Satisfiability of Equality Equations
• 947Most Stones Removed with Same Row or Column
• 1202Smallest String With Swaps
• 305Number of Islands IIpremium — land appears cell by cell

how it works

1. Check the degrees. Directed: every node has out = in, except possibly one start with one extra edge out and one end with one extra edge in. Undirected: zero or two nodes of odd degree.
2. From the start, walk: take an unused edge, cross it off, continue from where it leads.
3. When a node has no unused edges left, it is finished: append it to the route and return to the previous node, which tries its next unused edge.
4. Reverse the route. If it holds E + 1 nodes, every edge was used; if not, part of the graph was unreachable and there is no Euler path.

why it works

With balanced degrees, a walk can only get stuck at the end node: every other node it enters still has a way out. So the first node written down really is the end. Edges still unused at that moment form loops hanging off nodes on the stack; when backtracking reaches such a node, it walks the loop before writing the node down, which drops the loop into the route at exactly the right place. In the demo, the dead end 1 is reached far too early, and the loop 2 → 4 → 5 → 2 is spliced in later.

cost

Every edge is crossed once: O(V + E), plus O(E log E) to sort the lists when the smallest route in dictionary order is wanted.

watch out

• Smallest itinerary in dictionary order (LeetCode 332): take the smallest destination first — here each list is sorted descending and popped from the back.
• Do not DFS and undo edges when stuck: that is backtracking and can take exponential time. Hierholzer never undoes anything.
• Check degrees first. route.size() == E + 1 alone can pass for a sequence that is not a real path.
• The recursion goes E deep. For 10⁵ edges, use an explicit stack: the same loop, pushing instead of recursing.
• Undirected graphs: mark an edge used by its id, since both directions are one edge.

practice

• 332Reconstruct Itinerary — this exact walk, with airport codes
• 2097Valid Arrangement of Pairs — find the start from the degrees
• 753Cracking the Safe — an Euler circuit through a de Bruijn graph

how it works

1. DFS from every unvisited node. On entering u: disc[u] = low[u] = ++timer.
2. For each neighbor v: skip the edge you came in by — compare edge ids, not nodes, so a doubled edge still counts as a second way. If v was visited before, it is a back edge: low[u] = min(low[u], disc[v]).
3. Otherwise recurse into v, then pull its answer up: low[u] = min(low[u], low[v]).
4. If low[v] > disc[u], nothing under v reaches u or above except through u – v: a bridge. If low[v] ≥ disc[u] and u is not the root, u is an articulation point. The root is one only with two or more DFS children.

why it works

In an undirected DFS every edge that is not a tree edge joins a node to one of its ancestors — there are no cross edges. So v's subtree can only escape upward through back edges, and low[v] is the highest point it reaches that way. If that point is still below u, cutting u – v strands the whole subtree; if it is no higher than u, removing u does.

cost

A single DFS: O(V + E) time, O(V) memory.

watch out

• Skip the parent by edge id, not by parent node. With parallel edges, the second copy is a genuine second path.
• For back edges take disc[v], not low[v]: low[v] may route through the very node you are testing.
• The recursion goes V deep; LeetCode 1192 has 10⁵ nodes. If it crashes, raise the stack size or switch to an explicit stack.
• Run the DFS from every unvisited node — the graph may come in pieces.
• Directed graphs need a different tool: strongly connected components (Tarjan or Kosaraju).

practice

• 1192Critical Connections in a Network — exactly the bridges
• 1568Minimum Number of Days to Disconnect Island — 0, 1 or 2; a cut cell means 1