Advanced graph

1 · Why these matter

The Tier A graph trio. BFS, DFS, Dijkstra. Solves "is there a path", "shortest unweighted path", "shortest non-negative weighted path". For about 80% of interview graph questions, that's all you need. The other 20%. Senior-loop hards. Compete in companies. Codeforces-style contests. Require a specific advanced algorithm that none of the trio can express.

• Negative edge weights. Dijkstra is wrong. Negative weights break the "first time we settle a node, we have the shortest path" invariant. Use Bellman-Ford O(VE) or SPFA. Bellman-Ford also detects negative cycles, which Dijkstra can't even define.
• Huge search spaces with a good distance estimate. A* is Dijkstra plus a heuristic. The right heuristic prunes 99% of the explored nodes. Used in pathfinding, puzzle solvers, route planners.
• Structural properties of directed graphs. Strongly connected components (SCC): Tarjan O(V+E) or Kosaraju O(V+E). The building block for 2-SAT, condensation, deadlock detection.
• Structural properties of undirected graphs. Bridges are edges whose removal disconnects the graph. Articulation points are vertices whose removal disconnects. Both via low-link in one DFS.
• Bipartite matching. Pair up jobs with workers, students with schools, tasks with machines. Hopcroft-Karp O(E√V) or simpler augmenting-paths O(VE). The Hungarian algorithm for weighted matching.
• Maximum flow / minimum cut. The most general "throughput" question. Edmonds-Karp O(VE²), Dinic's O(V²E) or O(E√V) on unit graphs. Max-flow min-cut is the master theorem behind dozens of "is this configuration feasible" questions.

2 · Bellman-Ford: the negative-weight tool

The problem. Single-source shortest paths on a weighted directed graph where edge weights can be negative. Bellman-Ford handles it in O(VE), and detects negative cycles on the way out.

The idea

A shortest path on a graph with V vertices uses at most V−1 edges (no repeats, otherwise there's a cycle). So if we relax every edge V−1 times, every shortest distance must have stabilised. If one more round of relaxations still improves anything, there's a negative cycle.

Pseudocode:
    dist[source] = 0; dist[v] = +inf for all other v
    repeat V - 1 times:
        for each edge (u, v, w) in graph:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    // negative-cycle check
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:
            report "negative cycle reachable from source"

Go implementation

type Edge struct {
    From, To int
    Weight   int
}

// bellmanFord returns shortest distances from source, and whether a
// negative cycle is reachable from source.
func bellmanFord(n int, edges []Edge, source int) ([]int, bool) {
    const INF = int(1e18)
    dist := make([]int, n)
    for i := range dist {
        dist[i] = INF
    }
    dist[source] = 0

    // V - 1 rounds of relaxation
    for i := 0; i < n-1; i++ {
        updated := false
        for _, e := range edges {
            if dist[e.From] == INF {
                continue                 // skip unreachable so far
            }
            if dist[e.From]+e.Weight < dist[e.To] {
                dist[e.To] = dist[e.From] + e.Weight
                updated = true
            }
        }
        if !updated {
            break                        // converged early
        }
    }

    // negative-cycle detection: one more pass
    for _, e := range edges {
        if dist[e.From] == INF {
            continue
        }
        if dist[e.From]+e.Weight < dist[e.To] {
            return dist, true            // negative cycle exists
        }
    }
    return dist, false
}

When Bellman-Ford, when Dijkstra

Walkthrough: LC 787 Cheapest Flights Within K Stops

Problem. Cities connected by directed flights with prices. Find the cheapest price from src to dst using at most k stops (i.e. at most k + 1 edges). Edge weights are positive, so why not Dijkstra? Because Dijkstra optimises total cost while ignoring the hop budget: a cheap path with too many stops is invalid.

Bellman-Ford with exactly k + 1 rounds is the clean solution. After round i, dist[v] is the cheapest cost from src using at most i edges. Key wrinkle: use the previous round's distances when relaxing; otherwise one round can "stack" multiple edges.

func findCheapestPrice(n int, flights [][]int, src, dst, k int) int {
    const INF = int(1e18)
    dist := make([]int, n)
    for i := range dist {
        dist[i] = INF
    }
    dist[src] = 0

    // k + 1 rounds = paths of at most k + 1 edges = at most k stops
    for i := 0; i <= k; i++ {
        snapshot := make([]int, n)
        copy(snapshot, dist)             // CRUCIAL — relax against snapshot
        for _, f := range flights {
            u, v, w := f[0], f[1], f[2]
            if snapshot[u] == INF {
                continue
            }
            if snapshot[u]+w < dist[v] {
                dist[v] = snapshot[u] + w
            }
        }
    }

    if dist[dst] == INF {
        return -1
    }
    return dist[dst]
}

3 · SPFA: Bellman-Ford with a queue

SPFA (Shortest Path Faster Algorithm) is Bellman-Ford with a small optimisation: only nodes whose distance changed in the previous round can possibly cause relaxations in the current round. So put them in a queue, process one at a time, push neighbours when they get relaxed. Average case it's noticeably faster than naive Bellman-Ford; worst case it's still O(VE).

func spfa(n int, adj [][]Edge, source int) ([]int, bool) {
    const INF = int(1e18)
    dist := make([]int, n)
    for i := range dist {
        dist[i] = INF
    }
    dist[source] = 0

    inQueue := make([]bool, n)
    count := make([]int, n)              // number of times each vertex enqueued
    q := []int{source}
    inQueue[source] = true

    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        inQueue[u] = false

        for _, e := range adj[u] {
            if dist[u]+e.Weight < dist[e.To] {
                dist[e.To] = dist[u] + e.Weight
                if !inQueue[e.To] {
                    q = append(q, e.To)
                    inQueue[e.To] = true
                    count[e.To]++
                    if count[e.To] >= n {
                        return dist, true   // negative cycle
                    }
                }
            }
        }
    }
    return dist, false
}

4 · A* search: Dijkstra with a brain

A* is the heuristic-guided version of Dijkstra. Instead of always expanding the node with the smallest g(n) (cost from start), A* expands the node with the smallest f(n) = g(n) + h(n), where h(n) is an estimate of the cost from n to the goal.

Admissibility: the rule that keeps A* optimal

A heuristic is admissible if it never overestimates the true remaining cost. h(n) ≤ h*(n) for all n. As long as h is admissible, A* returns the optimal path. If h over-estimates even slightly, A* may return a suboptimal path and find it "quickly": fast but wrong.

• h(n) = 0 everywhere. A* degenerates to Dijkstra. Always admissible, never helpful.
• h(n) = true remaining cost. A* expands only nodes on an optimal path. Admissible by construction but usually uncomputable; if you could compute it you wouldn't need the search.
• h(n) somewhere in between. The art. For grids: Manhattan distance (4-connected), Chebyshev (8-connected), Euclidean (any-angle). Each is admissible for its movement model.

Diagram: A* prunes the search

Both algorithms find the same optimal path. Dijkstra explores in a disc around the start until it touches the goal; A* with an admissible heuristic biases exploration toward the goal and ends up looking at a fraction of the cells.

Go implementation

import "container/heap"

type aItem struct {
    node, f int
}
type aHeap []aItem
func (h aHeap) Len() int            { return len(h) }
func (h aHeap) Less(i, j int) bool  { return h[i].f < h[j].f }
func (h aHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *aHeap) Push(x any)         { *h = append(*h, x.(aItem)) }
func (h *aHeap) Pop() any           { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

// aStar returns the shortest distance from start to goal.
// adj is an adjacency list of (neighbour, edge-cost) pairs.
// h is an admissible heuristic h(n) <= true cost from n to goal.
func aStar(n, start, goal int, adj [][][2]int, h func(int) int) int {
    const INF = int(1e18)
    g := make([]int, n)
    for i := range g {
        g[i] = INF
    }
    g[start] = 0

    open := &aHeap{}
    heap.Push(open, aItem{start, h(start)})

    for open.Len() > 0 {
        it := heap.Pop(open).(aItem)
        u := it.node
        if u == goal {
            return g[u]
        }
        // Skip stale heap entries — common A* optimisation
        if it.f > g[u]+h(u) {
            continue
        }
        for _, e := range adj[u] {
            v, w := e[0], e[1]
            cand := g[u] + w
            if cand < g[v] {
                g[v] = cand
                heap.Push(open, aItem{v, cand + h(v)})
            }
        }
    }
    return -1
}

Walkthrough: LC 1091 Shortest Path in Binary Matrix

Problem. N×N grid, 0 = open and 1 = blocked. Move from top-left to bottom-right in 8 directions. Return the shortest path length (number of cells), or −1.

BFS works in O(N²) since edges are unweighted. A* with the Chebyshev distance as heuristic (h(r, c) = max(N-1-r, N-1-c)) is the lower bound on remaining cells in 8-connected movement. It's admissible and usually visits far fewer cells than BFS.

func shortestPathBinaryMatrix(grid [][]int) int {
    n := len(grid)
    if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
        return -1
    }

    h := func(r, c int) int {
        // Chebyshev distance — admissible for 8-connected grid
        dr := n - 1 - r
        dc := n - 1 - c
        if dr > dc {
            return dr + 1
        }
        return dc + 1
    }

    // Open list ordered by g + h
    type state struct{ r, c, g, f int }
    open := &aHeap{}                     // reuse the heap from above
    g := make([][]int, n)
    for i := range g {
        g[i] = make([]int, n)
        for j := range g[i] {
            g[i][j] = 1<<30
        }
    }
    g[0][0] = 1
    heap.Push(open, aItem{0, 1 + h(0, 0)})  // pack (r,c) into one int if needed

    // (For brevity the code packs (r, c) as r*n+c; expand similarly to aStar above.)
    // ...return g[n-1][n-1] or -1.
    return -1
}

5 · Tarjan's SCC: one DFS, low-link, one stack

A strongly connected component in a directed graph is a maximal set of vertices where every vertex can reach every other. Tarjan's algorithm finds all SCCs in a single DFS, in O(V+E). The trick is a per-vertex value called lowlink: the smallest discovery index reachable from the subtree rooted at v, using tree edges plus at most one back edge.

The pieces

• disc[v]: the order in which v was first visited (DFS discovery time).
• low[v]: the lowest disc value reachable from v's DFS subtree, via tree edges and at most one back edge to a vertex still on the stack.
• The stack: every vertex pushed when discovered, popped when its SCC is finalised. A vertex is on the stack iff its SCC hasn't been emitted yet.
• The SCC condition: when low[v] == disc[v] at the end of DFS(v), v is the "root" of an SCC. Pop the stack down to and including v; those are the component.

Diagram: SCC stack and back edges

Go implementation

type tarjan struct {
    n         int
    adj       [][]int
    disc, low []int
    onStack   []bool
    stack     []int
    timer     int
    sccs      [][]int
}

func newTarjan(n int, adj [][]int) *tarjan {
    return &tarjan{
        n:       n,
        adj:     adj,
        disc:    make([]int, n),
        low:     make([]int, n),
        onStack: make([]bool, n),
    }
}

func (t *tarjan) run() [][]int {
    for i := range t.disc {
        t.disc[i] = -1
    }
    for i := 0; i < t.n; i++ {
        if t.disc[i] == -1 {
            t.dfs(i)
        }
    }
    return t.sccs
}

func (t *tarjan) dfs(u int) {
    t.timer++
    t.disc[u], t.low[u] = t.timer, t.timer
    t.stack = append(t.stack, u)
    t.onStack[u] = true

    for _, v := range t.adj[u] {
        if t.disc[v] == -1 {
            t.dfs(v)
            // tree edge — propagate low from child
            if t.low[v] < t.low[u] {
                t.low[u] = t.low[v]
            }
        } else if t.onStack[v] {
            // back edge to vertex still on stack — use its disc, NOT low
            if t.disc[v] < t.low[u] {
                t.low[u] = t.disc[v]
            }
        }
        // else: cross edge to a finished SCC — ignore
    }

    // Root of an SCC — pop until we hit u
    if t.low[u] == t.disc[u] {
        var comp []int
        for {
            top := t.stack[len(t.stack)-1]
            t.stack = t.stack[:len(t.stack)-1]
            t.onStack[top] = false
            comp = append(comp, top)
            if top == u {
                break
            }
        }
        t.sccs = append(t.sccs, comp)
    }
}

6 · Kosaraju's SCC: two DFS, simpler to remember

Kosaraju gets to the same answer as Tarjan with two passes, no lowlink, no stack-membership flag. Conceptually it's easier: many implementations prefer it for teaching even though Tarjan is one DFS and faster in practice.

1. DFS pass 1. On the original graph, push each vertex onto a stack as its DFS finishes.
2. Transpose. Build the reverse graph (every edge reversed).
3. DFS pass 2. Pop vertices from the stack in order; for each unvisited one, DFS on the transposed graph. Each such DFS visits exactly one SCC.

func kosaraju(n int, adj [][]int) [][]int {
    // PASS 1 — finish order on the original graph
    visited := make([]bool, n)
    var order []int
    var dfs1 func(int)
    dfs1 = func(u int) {
        visited[u] = true
        for _, v := range adj[u] {
            if !visited[v] {
                dfs1(v)
            }
        }
        order = append(order, u)
    }
    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs1(i)
        }
    }

    // TRANSPOSE
    radj := make([][]int, n)
    for u := 0; u < n; u++ {
        for _, v := range adj[u] {
            radj[v] = append(radj[v], u)
        }
    }

    // PASS 2 — DFS in reverse finish order on transpose
    for i := range visited {
        visited[i] = false
    }
    var sccs [][]int
    var comp []int
    var dfs2 func(int)
    dfs2 = func(u int) {
        visited[u] = true
        comp = append(comp, u)
        for _, v := range radj[u] {
            if !visited[v] {
                dfs2(v)
            }
        }
    }
    for i := len(order) - 1; i >= 0; i-- {
        u := order[i]
        if !visited[u] {
            comp = nil
            dfs2(u)
            sccs = append(sccs, comp)
        }
    }
    return sccs
}

7 · Bridges & articulation points: same low-link, undirected

A bridge in an undirected graph is an edge whose removal disconnects the graph. An articulation point is a vertex whose removal disconnects. Both fall out of one DFS that maintains the same disc / low values as Tarjan's SCC, adapted slightly for undirected edges.

The conditions

• Bridge. Edge (u, v) where v is a child of u in the DFS tree and low[v] > disc[u]. Meaning: no back edge from v's subtree reaches u or higher, so the edge is the only connection.
• Articulation point (non-root). Vertex u with a DFS-tree child v such that low[v] ≥ disc[u].
• Articulation point (root). The root of the DFS tree is an articulation point iff it has at least 2 DFS-tree children.

Diagram: bridges in an undirected graph

Go implementation: bridge finder

func criticalConnections(n int, connections [][]int) [][]int {
    adj := make([][]int, n)
    for _, c := range connections {
        u, v := c[0], c[1]
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u)
    }

    disc := make([]int, n)
    low := make([]int, n)
    for i := range disc {
        disc[i] = -1
    }
    var bridges [][]int
    timer := 0

    var dfs func(u, parent int)
    dfs = func(u, parent int) {
        timer++
        disc[u], low[u] = timer, timer
        for _, v := range adj[u] {
            if v == parent {
                continue              // skip the edge we came from
            }
            if disc[v] == -1 {
                dfs(v, u)
                if low[v] < low[u] {
                    low[u] = low[v]
                }
                // BRIDGE TEST
                if low[v] > disc[u] {
                    bridges = append(bridges, []int{u, v})
                }
            } else {
                // back edge
                if disc[v] < low[u] {
                    low[u] = disc[v]
                }
            }
        }
    }

    for i := 0; i < n; i++ {
        if disc[i] == -1 {
            dfs(i, -1)
        }
    }
    return bridges
}

8 · Bipartite matching: augmenting paths

A matching in a bipartite graph (vertices split into L and R, edges only between the parts) is a set of edges with no shared endpoints. The maximum matching problem: find the largest such set. Two algorithms: simple augmenting-path DFS (Hungarian DFS, O(VE)) and Hopcroft-Karp (O(E√V)).

The augmenting-path idea

An augmenting path alternates unmatched and matched edges, starts at an unmatched L vertex, ends at an unmatched R vertex. Flipping the matched/unmatched status along the path increases the matching by 1. Berge's theorem: a matching is maximum iff no augmenting path exists. So: while you can find one, augment.

Go implementation: Hungarian DFS

// matchL[u] = R-vertex matched with L-vertex u, or -1
// matchR[v] = L-vertex matched with R-vertex v, or -1
// adj[u] = list of R-vertices reachable from L-vertex u

func maxBipartiteMatching(nL, nR int, adj [][]int) int {
    matchR := make([]int, nR)
    for i := range matchR {
        matchR[i] = -1
    }

    var tryMatch func(u int, seen []bool) bool
    tryMatch = func(u int, seen []bool) bool {
        for _, v := range adj[u] {
            if seen[v] {
                continue
            }
            seen[v] = true
            if matchR[v] == -1 || tryMatch(matchR[v], seen) {
                matchR[v] = u
                return true
            }
        }
        return false
    }

    matched := 0
    for u := 0; u < nL; u++ {
        seen := make([]bool, nR)
        if tryMatch(u, seen) {
            matched++
        }
    }
    return matched
}

Hopcroft-Karp speeds this up by finding many disjoint augmenting paths per BFS-layered phase. The bound O(E√V) is tight and matters only on large bipartite graphs (V > 10⁴). For interview-scale, the simple DFS version is sufficient.

9 · Max-flow / min-cut

The setup. A directed graph with edge capacities, a source s and a sink t. Find the maximum amount of "flow" that can be pushed from s to t such that each edge carries no more than its capacity and every intermediate vertex conserves flow (in = out).

The residual graph: the key concept

For every edge u → v with capacity c, the residual graph has a forward edge with residual capacity c − f (how much more you can push) and a reverse edge with residual capacity f (how much you can "undo"). The reverse edges let later augmenting paths cancel earlier flow decisions. Without them, greedy flow gets stuck in suboptimal local maxima.

Ford-Fulkerson: the meta-algorithm

Ford-Fulkerson:
    while there exists an augmenting path P from s to t in the residual graph:
        bottleneck = min residual capacity along P
        push 'bottleneck' units of flow along P
        update residual capacities
    return total flow

(Termination requires integer capacities; otherwise can loop forever.)

Edmonds-Karp: Ford-Fulkerson with BFS

Edmonds-Karp specifies the augmenting path is the shortest one (fewest edges), found by BFS. This gives O(VE²) worst case, polynomial in graph size: Ford-Fulkerson alone is only pseudo-poly (O(F · E) where F is max flow value).

// cap[u][v] = remaining capacity from u to v
// Returns total max flow from s to t.

func edmondsKarp(n int, cap [][]int, s, t int) int {
    total := 0
    for {
        parent := make([]int, n)
        for i := range parent {
            parent[i] = -1
        }
        parent[s] = s
        q := []int{s}
        for len(q) > 0 && parent[t] == -1 {
            u := q[0]
            q = q[1:]
            for v := 0; v < n; v++ {
                if parent[v] == -1 && cap[u][v] > 0 {
                    parent[v] = u
                    q = append(q, v)
                }
            }
        }
        if parent[t] == -1 {
            break                        // no augmenting path
        }
        // Find bottleneck capacity along the path
        bottleneck := int(1e18)
        for v := t; v != s; v = parent[v] {
            if cap[parent[v]][v] < bottleneck {
                bottleneck = cap[parent[v]][v]
            }
        }
        // Update capacities — forward decreased, reverse increased
        for v := t; v != s; v = parent[v] {
            u := parent[v]
            cap[u][v] -= bottleneck
            cap[v][u] += bottleneck      // residual back-edge
        }
        total += bottleneck
    }
    return total
}

Dinic's: level graph plus blocking flow

Dinic's algorithm partitions the residual graph into BFS layers (the level graph), then finds a blocking flow, a flow that saturates at least one edge on every s-to-t path in the level graph, using DFS. Repeat until no augmenting path exists. Complexity: O(V²E) general, O(E√V) on unit-capacity graphs (which includes bipartite matching), O(E√E) on bipartite graphs in the Hopcroft-Karp sense.

Max-flow min-cut theorem

Why it matters. Many problems framed as "remove a minimum set of edges / vertices to disconnect X from Y" reduce to min-cut, which reduces to max-flow. Project-selection, image segmentation, baseball elimination, escape-room puzzles: all min-cut in disguise.

10 · Worked hard. LC 1192 Critical Connections

Problem. A network of n servers, numbered 0 to n−1, connected by undirected connections. A critical connection is an edge whose removal disconnects some pair of servers. Return all critical connections.

Recognise the pattern

• "Edge whose removal disconnects" is the textbook bridge definition. No DP, no flow, no clever insight needed: this is Tarjan's bridge algorithm verbatim.
• One DFS with disc / low. Compute disc[u] and low[u] for each vertex; an edge (u, v) is a bridge iff low[v] > disc[u] where v is a DFS-tree child of u.
• Total O(V + E). Single DFS, constant work per edge.

Trace through a small example

Take n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]. The graph: triangle 0-1-2, plus edge 1-3. Which edges are bridges?

Edge (1, 3): low[3] = 4 > disc[1] = 2 → bridge. All triangle edges: low of the subtree reaches back to disc[u] or lower → not bridges. Correct answer: [[1, 3]].

Full Go solution

func criticalConnectionsLC1192(n int, connections [][]int) [][]int {
    adj := make([][]int, n)
    for _, c := range connections {
        adj[c[0]] = append(adj[c[0]], c[1])
        adj[c[1]] = append(adj[c[1]], c[0])
    }

    disc := make([]int, n)
    low := make([]int, n)
    for i := range disc {
        disc[i] = -1
    }
    var out [][]int
    timer := 0

    var dfs func(u, parent int)
    dfs = func(u, parent int) {
        timer++
        disc[u] = timer
        low[u] = timer

        for _, v := range adj[u] {
            if v == parent {
                continue
            }
            if disc[v] == -1 {
                dfs(v, u)
                if low[v] < low[u] {
                    low[u] = low[v]
                }
                if low[v] > disc[u] {
                    out = append(out, []int{u, v})
                }
            } else if disc[v] < low[u] {
                low[u] = disc[v]
            }
        }
    }

    for i := 0; i < n; i++ {
        if disc[i] == -1 {
            dfs(i, -1)
        }
    }
    return out
}

11 · Worked hard. LC 787 Cheapest Flights Within K Stops

Walked already in section 2: here's the deeper why.

Why Dijkstra doesn't quite work

Dijkstra would find the cheapest path ignoring the hop constraint, which may be too long. You could try to retrofit by tracking (city, stops) pairs in the heap, expanding only states with stops ≤ k. That works and is sometimes faster on sparse graphs, but the state space blows up to O(V · K), and the heap can hold duplicates of (city, stops) pairs.

Why Bellman-Ford fits naturally

Each round of Bellman-Ford extends paths by exactly one more edge. After round i, dist[v] is the cheapest cost using at most i edges. So k + 1 rounds gives "at most k stops" exactly. The snapshot (copy(snapshot, dist) at the start of each round) ensures one round adds one edge, not a chain.

Alternative: Dijkstra with state expansion

// State: (cost, city, stops_used).
// Heap-ordered by cost. Expand only if stops_used < k.
// Faster on graphs where most short paths cost much more than the optimum.
// Bellman-Ford is the cleaner "correct by construction" answer.

12 · Sister algorithms worth knowing the names of

• Johnson's algorithm: all-pairs shortest paths with possibly negative weights, no negative cycles. O(V² log V + VE). Trick: add a virtual vertex with zero-weight edges to all, run Bellman-Ford from it to get vertex potentials, then re-weight all edges to be non-negative and run V Dijkstras. Cleaner than Floyd-Warshall O(V³) when the graph is sparse.
• 2-SAT: satisfiability for boolean formulas in 2-CNF. Each clause (a ∨ b) becomes implications ¬a → b and ¬b → a. Build an implication graph on 2n literals, run SCC. Formula is satisfiable iff no variable and its negation are in the same SCC. Linear time.
• Borůvka's MST: minimum spanning tree by parallel contractions; each round every component picks its cheapest outgoing edge. O((V+E) log V) but parallelises trivially, making it the algorithm of choice for distributed MST.
• Kruskal with link-cut trees, when you need MST dynamically (edges inserted/removed online), maintain a forest via link-cut trees in amortised O(log n) per op.
• Eulerian path / Hierholzer's algorithm: traversal that uses every edge exactly once. O(V + E). LC 332 (Reconstruct Itinerary) is Hierholzer's.
• Chinese Postman: minimum-weight closed walk that traverses every edge. Reduces to matching odd-degree vertices.
• Stoer-Wagner global min-cut: minimum cut between any pair of vertices in an undirected graph. O(V³) but no max-flow needed.
• Push-relabel: alternative max-flow algorithm with better practical performance than Edmonds-Karp on dense graphs. O(V² √E) in the highest-label variant.

13 · How to solve hard graph problems step-by-step

1. Classify the graph. Directed or undirected? Weighted or unweighted? Sparse (E ≈ V) or dense (E ≈ V²)? Edges fixed or evolving? The answer rules out 60% of candidate algorithms immediately.
2. Inspect the weights. Non-negative weights → Dijkstra. Negative weights but no negative cycle → Bellman-Ford or Johnson's. Weights ∈ {0, 1} → 0/1 BFS (deque, O(V+E)). Weights all 1 → plain BFS.
3. Identify the query shape. "Single source to all" → Dijkstra / Bellman-Ford. "All pairs" → Floyd-Warshall O(V³) or Johnson's. "Specific s to specific t" with constraints → variants of the above.
4. Look for a structural property. "Bridges" / "articulation points" → low-link DFS. "Strongly connected components" → Tarjan or Kosaraju. "Topological order exists" → Kahn or DFS. "Bipartite" → 2-colouring.
5. Reduce to flow or matching. "Maximum number of disjoint paths" → max-flow. "Match jobs to workers" → bipartite matching. "Minimum edges to remove to disconnect X from Y" → min-cut = max-flow.
6. Look for hop / cost constraints. "Within K stops" → bounded-rounds Bellman-Ford or state-augmented Dijkstra. "Within budget B" → DP over (vertex, budget).
7. If none fit, think about state augmentation. Many "graph + constraint" problems become standard graph problems on the product graph (state, position). The graph just got bigger.

14 · Complexity reference

15 · What breaks

• Bellman-Ford without the negative-cycle pass. If a negative cycle is reachable, the distances are nonsense (they keep dropping each round). The extra pass detects it; without it, "shortest path" is undefined and your code lies.
• Bellman-Ford without the snapshot in bounded-hops mode. Without copying dist at the start of each round, one round can chain multiple edges, and "at most k stops" silently becomes "any number of stops". This is the LC 787 trap.
• A* with an inadmissible heuristic. Returns the first path the heuristic finds, which may not be optimal. Manhattan distance on a 4-connected grid is admissible; using it on an 8-connected grid is also admissible (it overestimates "movements" but underestimates "diagonal moves count as one"... it's admissible there too, just loose). Euclidean on an 8-connected grid is admissible; Euclidean on Manhattan-only movement is inadmissible.
• A* with a non-consistent (but admissible) heuristic. May re-expand nodes; you need to allow updates after a node is popped. Most implementations get this right by skipping stale entries in the heap.
• Tarjan SCC using low[v] on back edges. The classical formulation uses disc[v] on back edges; low[v] works in many cases but breaks on certain back-edge configurations. Stick to disc[v].
• Bridge algorithm without parent-edge handling. In undirected DFS, the edge to the parent looks like a back edge. Skip it explicitly. On parallel edges, track the edge index, not the parent vertex.
• Max-flow with very large capacities. Ford-Fulkerson with adversarial path choice can take O(F · E) augmentations where F is the max flow value: exponential in input size. Edmonds-Karp (BFS) bounds it polynomially. Always pick BFS for the augmenting path unless you know your graph well.
• Max-flow with floating-point capacities. Ford-Fulkerson may not terminate. There's a famous example by Zwick using Fibonacci-like capacities. Use rationals or scale to integers.
• Recursive DFS at scale. 10⁵ vertices in a near-line graph blows the default stack in most languages. Either bump the stack or rewrite iteratively. Tarjan and bridges are both prone to this on LeetCode.
• Forgetting reverse edges in max-flow. Without residual back-edges, "cancellation" of flow can't happen and the algorithm returns a suboptimal flow. Every edge addition must add both a forward and a reverse residual edge.

16 · Where this gets asked

17 · Try it yourself

Cheapest Flights Within K Stops · LC 787

Bellman-Ford with k + 1 rounds; snapshot the distance array each round. Hint: the bug-magnet is forgetting the snapshot, without it, a single round can chain multiple edges and you'll silently allow more than k stops.

Critical Connections · LC 1192

Tarjan's bridge algorithm with low-link. Hint: track disc and low, skip the parent edge in undirected DFS, an edge (u, v) is a bridge iff low[v] > disc[u]. Watch for the stack-overflow at n = 10⁵.

Shortest Path in Binary Matrix · LC 1091

BFS works; A* with Chebyshev heuristic explores fewer cells. Hint: in 8-connected movement, h(r, c) = max(N−1−r, N−1−c) is admissible. Use it as the priority along with g.

Network Delay Time · LC 743

Single-source shortest path; Dijkstra fits. Hint: classic warm-up before the harder Bellman-Ford / A* questions. If you can't solve this fast, the advanced ones aren't ready yet.

Stretch: Reconstruct Itinerary · LC 332

Eulerian path via Hierholzer's algorithm. Hint: greedy DFS with edges visited in lexicographic order; emit vertices on the way back up the call stack. Reverse the emission list at the end.

Further reading

• CP-Algorithms: graph section. The single best free reference for advanced graph algorithms. Concise pseudocode, proofs, complexity. https://cp-algorithms.com/graph/.
• Sedgewick & Wayne: Algorithms (4th ed), Chapter 4. Graphs from BFS to flow. Java-focused but the algorithm descriptions are language-agnostic.
• CLRS: Introduction to Algorithms, Chapters 22–26. The textbook treatment. Dense but definitive, especially the max-flow chapter.
• MIT 6.006 lectures (OCW). Erik Demaine's lectures on shortest paths, max-flow, and amortised analysis are uniquely good free videos.
• Tarjan's original paper (1972): "Depth-first search and linear graph algorithms". Short, dense, foundational. Worth reading once for the SCC and bridges algorithms.
• Kleinberg & Tardos: Algorithm Design. The matching and flow chapters are particularly clear, with motivating real-world reductions.
• Adjacent: graph algorithms (Tier B page). The BFS/DFS/Dijkstra foundation this page builds on.
• Adjacent: union-find. The other graph data structure; especially relevant for offline-MST and Kruskal.