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"... actually 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.