Advanced graph algorithms

Beyond traversal and shortest paths, graph work is largely about recognising which known problem the one in front of you actually is. This guide covers minimum spanning trees and the cut property behind both standard algorithms, near-constant-time disjoint sets, strongly connected components and the acyclic condensation they expose, bridges and articulation points from a single low-link pass, all-pairs paths and when each approach wins, and network flow together with the modelling moves — residual edges, vertex splitting — that make matching and partitioning problems into flow instances. It is equally explicit about hardness: which of these problems are NP-complete, what a valid response to that looks like, and why an approximation ratio is a result while an unbounded heuristic is not.

minimum spanning trees

A minimum spanning tree connects every vertex of a connected undirected graph at the least total edge weight, and it is not a shortest-path tree.

The cut property justifies both standard algorithms: the lightest edge crossing any partition of the vertices belongs to some minimum spanning tree.

A spanning tree is not a shortest-path tree.

      1        1
   A ---- B ---- C          MST total = 2, and the MST path A->B->C costs 2
    \____________/          Direct A->C edge costs 1.5, so the MST path is 33% worse
          1.5               than the shortest path, while the tree itself is minimal.

Interview trap. Assuming the path between two vertices in a minimum spanning tree is their shortest path is false, and a triangle with weights one, one, and one and a half shows it.

Engineering practice. Use a spanning tree when the objective is total connection cost, and a shortest-path tree when it is per-pair distance.

Kruskal versus Prim

Kruskal sorts edges and unions components; Prim grows one component using a priority queue, and the choice follows from graph density.

Kruskal costs O(E log E) dominated by the sort and suits sparse graphs; Prim with a heap costs O(E log V) and suits dense graphs, where a matrix-based version can reach O(V squared).

Sparse favours Kruskal; dense favours Prim.

Algorithm	Bound	Needs	Best when
Kruskal	O(E log E)	all edges up front	E close to V
Prim (binary heap)	O(E log V)	a neighbour function	E close to V^2
Prim (matrix)	O(V^2)	adjacency matrix	very dense

Interview trap. Treating them as interchangeable ignores that Kruskal needs all edges up front while Prim can work with an implicit neighbour function.

Engineering practice. Choose Kruskal for sparse edge lists and Prim when neighbours are generated on demand or the graph is dense.

union-find with path compression

Disjoint-set union with path compression and union by rank performs each operation in near-constant amortised time.

Path compression flattens the tree during find, and union by rank keeps the taller tree as the root, so the combined bound is the inverse Ackermann function of the element count.

Both optimisations, or the bound is logarithmic.

# Union in a chain, 1,000,000 elements:
#   no rank, no compression -> find() walks up to 1,000,000 links
#   rank only               -> O(log n)
#   rank + compression      -> effectively O(1) amortised

Interview trap. Implementing only one of the two optimisations leaves a logarithmic bound, which shows up as a slow Kruskal on large inputs.

Engineering practice. Implement both, and verify with a workload that unions in a chain, which is the pattern that exposes a missing rank rule.

strongly connected components

A strongly connected component is a maximal set of vertices mutually reachable in a directed graph, and finding them exposes the graph's acyclic skeleton.

Tarjan's algorithm finds them in one depth-first pass using discovery indices and low-link values; Kosaraju uses two passes with the reversed graph.

Mutual reachability, not connectivity of the undirected shadow.

A -> B -> C -> A      one SCC {A, B, C}
D -> A                 D is weakly connected to them and reaches them,
                       but nothing reaches D: {D} is its own SCC.

Interview trap. Treating weakly connected components — connectivity in the underlying undirected graph — as strongly connected merges vertices that cannot reach each other.

Engineering practice. State which notion of connectivity the problem needs, and use the condensation into a directed acyclic graph when the answer is about component structure.

the condensation graph

Contracting each strongly connected component to a single vertex always yields a directed acyclic graph.

This reduces many problems on general directed graphs to problems on acyclic ones, where dynamic programming over a topological order applies.

Contracting SCCs yields a DAG for component-level propagation, not a shortcut through NP-hard internal paths.

# 1,000,000-vertex web graph with a large strongly connected core:
# condensation turns component reachability and aggregate propagation into a
# linear DP over the component DAG. It does not solve longest simple paths
# inside an SCC; that problem remains NP-hard.

Interview trap. Running an acyclic-graph algorithm on the original graph without condensing loops forever or produces answers that depend on the traversal order.

Engineering practice. Condense first when the graph may contain cycles, and carry component aggregates onto the contracted vertices.

bridges and articulation points

A bridge is an edge whose removal disconnects the graph, and an articulation point is a vertex with the same property.

Both are found in one depth-first pass by comparing each subtree's lowest reachable discovery time with the current vertex's, which detects whether a back edge bypasses the connection.

One DFS with low-links, not E connectivity checks.

def dfs(u, parent_edge):
    disc[u] = low[u] = next(timer)
    for v, edge_id in adj[u]:
        if edge_id == parent_edge: continue
        if v in disc: low[u] = min(low[u], disc[v])
        else:
            dfs(v, edge_id); low[u] = min(low[u], low[v])
            if low[v] > disc[u]: bridges.append((u, v))    # no back edge bypasses it

Tracking the parent edge, not just the parent vertex, also handles parallel edges correctly. Removing each edge and re-running costs O(E(V+E)); this is O(V+E).

Interview trap. Testing each edge by removing it and rerunning connectivity is correct but costs O(E(V+E)), which is impractical at any real scale.

Engineering practice. Use the low-link computation, and handle the root of the depth-first tree as a special case for articulation points.

all-pairs shortest paths

Floyd-Warshall computes shortest paths between every pair in O(V cubed) with a triple loop, and the loop order is not interchangeable.

The intermediate-vertex loop must be outermost, because the recurrence assumes all paths through earlier intermediates are already final.

The intermediate loop must be outermost.

for k in range(n):            # intermediate vertex - OUTERMOST
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Any other nesting reads paths through k that are not yet final, and the answers are wrong on many graphs.

Interview trap. Placing the intermediate loop innermost gives a plausible triple loop that computes wrong distances on many graphs.

Engineering practice. Fix the loop order in a comment, and validate against repeated Dijkstra on random graphs.

choosing between all-pairs approaches

Running Dijkstra from every vertex beats Floyd-Warshall on sparse graphs, and loses on dense ones.

Repeated Dijkstra costs O(V(V+E) log V), which is better than V cubed when E is much smaller than V squared.

Density decides.

V	E	Floyd-Warshall	Repeated Dijkstra
500	2,000	1.25 x 10^8	500 x 2,500 x 9 ≈ 1.1 x 10^7
500	240,000	1.25 x 10^8	500 x 240,500 x 9 ≈ 1.1 x 10^9

Interview trap. Reaching for Floyd-Warshall because it is simpler to write is a defensible choice, but claiming it is faster on sparse graphs is not.

Engineering practice. Compare the two bounds using the graph's actual density, and mention Johnson's algorithm when negative edges are present.

the A-star heuristic

A-star is Dijkstra with a heuristic added to the priority, and it is correct only if the heuristic never overestimates the remaining distance.

An admissible heuristic guarantees the optimal path, and a consistent one additionally guarantees each vertex is finalised once, as in Dijkstra.

Admissible means never overestimating; that is what preserves optimality.

def h(a, b):  # edge weights are physical road lengths
    return euclidean(a, b)          # <= true route length: admissible

# Multiplying h by 1.5 makes the search faster and the path possibly suboptimal.
# That is a trade to state, not a bug to hide.

Interview trap. Using an inadmissible heuristic makes the search faster and the answer possibly suboptimal, which is a trade that must be stated rather than hidden.

Engineering practice. Prove admissibility for the chosen heuristic, and say explicitly when optimality has been traded for speed.

maximum flow

The maximum flow through a network equals the capacity of its minimum cut, which is what makes flow a tool for partitioning problems.

Augmenting-path algorithms repeatedly push flow along a path with residual capacity and update the residual graph, including backward edges that allow flow to be rerouted.

Backward residual edges are what let flow be rerouted.

def add_edge(u, v, cap):
    graph[u].append([v, cap, len(graph[v])])
    graph[v].append([u, 0, len(graph[u]) - 1])   # the reverse edge, capacity 0

Without it the algorithm is greedy and stalls below the maximum.

Interview trap. Omitting the backward residual edges yields a greedy algorithm that gets stuck at a suboptimal flow.

Engineering practice. Build the residual graph with paired forward and backward edges, and verify the result against the minimum cut.

Edmonds-Karp and Dinic

Choosing the shortest augmenting path bounds the number of augmentations and makes maximum flow polynomial regardless of capacities.

Edmonds-Karp uses breadth-first search for an O(V E squared) bound; Dinic's level graph and blocking flows improve it substantially on most practical instances.

Shortest augmenting paths bound the number of augmentations.

Algorithm	Bound	Depends on capacities
DFS augmenting	O(E x maxflow)	yes - pathological on 10^9 capacities
Edmonds-Karp (BFS)	O(V E^2)	no
Dinic	O(V^2 E), O(E sqrt(V)) unit caps	no

Interview trap. A depth-first augmenting search has no polynomial bound in the capacities, and a contrived graph makes it take a number of steps proportional to the capacity values.

Engineering practice. Use breadth-first augmentation at minimum, and prefer Dinic when the graph is large or capacities are skewed.

bipartite matching as flow

Maximum bipartite matching is a maximum-flow instance with unit capacities, and Hopcroft-Karp solves it faster than general flow.

A source connects to one side and a sink to the other with unit capacities, so an integral maximum flow is exactly a maximum matching.

Unit capacities, so an integral max flow is a maximum matching.

source -> each left vertex   (capacity 1)
left    -> right on each edge (capacity 1)
right   -> sink               (capacity 1)

Greedy matching gets stuck at maximal-but-not-maximum; augmenting paths are the fix. Hopcroft-Karp: O(E sqrt(V)).

Interview trap. Greedy matching without augmenting paths gets stuck at a maximal but not maximum matching, which is the whole difficulty of the problem.

Engineering practice. Use augmenting paths, and reach for Hopcroft-Karp when the bipartite graph is large.

modelling with flow

Assignment, scheduling, and disjoint-path problems are often flow problems in disguise, and the modelling is the hard part.

Vertex capacities are modelled by splitting a vertex into an in-node and an out-node joined by an edge of that capacity.

Vertex capacities need a split into in- and out-nodes.

u  becomes  u_in --(cap = vertex capacity)--> u_out
Incoming edges land on u_in; outgoing edges leave u_out.

Edge-capacity flow on the unsplit graph silently permits solutions that violate the vertex limit.

Interview trap. Applying edge-capacity flow to a problem with vertex constraints silently permits solutions that violate them.

Engineering practice. Split constrained vertices explicitly, and check the model by verifying that an obviously invalid solution is infeasible.

Eulerian paths

An Eulerian path uses every edge exactly once and exists only under a precise degree condition.

An undirected connected graph has an Eulerian circuit when every vertex has even degree, and a path when exactly two have odd degree; the directed case compares in-degree and out-degree.

A degree condition, checkable in O(V).

Graph	Circuit exists	Path exists
Undirected, connected	every degree even	exactly two odd degrees
Directed, connected	in = out everywhere	one vertex out-in = 1, one in-out = 1

Hamiltonian looks similar and is NP-complete: the two must not be confused.

Interview trap. Confusing the Eulerian condition with the Hamiltonian problem is a category error: one is decidable in linear time and the other is NP-complete.

Engineering practice. Check the degree condition and connectivity first, then construct the path with Hierholzer's algorithm.

Hamiltonian paths and hardness

Finding a path visiting every vertex once is NP-complete, so no polynomial algorithm is known and exponential methods are expected.

The practical approaches are bitmask dynamic programming for small vertex counts, branch and bound, or approximation for the metric travelling-salesman case.

NP-complete; the answer is a bound, not an algorithm.

# n = 20: bitmask DP, O(2^n x n^2) ≈ 4.2 x 10^8 transitions -
#         the upper edge even in optimised compiled code, and usually too slow in Python
# n = 30:  9.7 x 10^11 - not feasible
# Beyond that: branch and bound, or metric approximation with a stated ratio.

Interview trap. Proposing a greedy or flow-based polynomial algorithm for a Hamiltonian problem indicates the hardness was not recognised.

Engineering practice. Name the hardness explicitly, then state the exponential bound achievable and the vertex count at which it stops being practical.

bitmask dynamic programming over subsets

Problems over subsets of a small vertex set are solved in O(2 to the V times V squared) by indexing states with a bitmask.

The state is the visited set plus the current vertex, and the transition adds one unvisited vertex, which covers the travelling-salesman path.

State is (visited set, current vertex).

INF = float("inf")
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0
for mask in range(1 << n):
    for u in range(n):
        if dp[mask][u] == INF or not mask >> u & 1: continue
        for v in range(n):
            if mask >> v & 1: continue
            nm = mask | 1 << v
            dp[nm][v] = min(dp[nm][v], dp[mask][u] + w[u][v])

Memory: 2^20 x 20 x 8 bytes ≈ 168 MB at n = 20. Compute it before implementing.

Interview trap. Assuming this scales beyond roughly twenty vertices ignores that both time and memory double per additional vertex.

Engineering practice. State the vertex limit the approach supports, and switch to approximation or heuristics beyond it.

graph colouring

Deciding whether a graph is three-colourable is NP-complete, while two-colourability is a linear-time bipartite test.

Greedy colouring by degree ordering gives a bound of one more than the maximum degree, which is often far from optimal but always valid.

Greedy gives Δ+1 colours - an upper bound, not an optimum.

# A 5-cycle needs 3 colours. Greedy in a bad vertex order uses 3 too,
# but on other graphs greedy can use many more than the chromatic number.
# Deciding 3-colourability is NP-complete.

Interview trap. Presenting a greedy colouring as minimal overstates the result; greedy is an upper bound, not an optimum.

Engineering practice. Use greedy for a valid assignment and say it is an upper bound, reserving exact methods for small instances.

the travelling-salesman approximation

For metric instances satisfying the triangle inequality, a minimum spanning tree gives a tour within twice the optimum, and Christofides improves the factor to one and a half.

Doubling the tree edges yields an Eulerian multigraph whose circuit shortcuts into a tour, and the triangle inequality is what makes the shortcut no worse.

MST doubling gives 2x; Christofides 1.5x - and only for metric instances.

# Triangle inequality required: d(a, c) <= d(a, b) + d(b, c).
# Shortcutting an Eulerian walk is only safe because of it.
# On a non-metric instance the ratio guarantee simply does not exist.

Interview trap. Applying the approximation to a non-metric instance gives no guarantee at all, because shortcutting can then increase cost.

Engineering practice. Verify the triangle inequality holds before quoting the ratio, and state the ratio rather than claiming optimality.

shortest paths on a directed acyclic graph

On an acyclic graph, shortest and longest paths are both computed in linear time by relaxing edges in topological order.

The topological order guarantees that when a vertex is processed, every path into it is already final, so no priority queue is needed.

Relax in topological order: linear, and longest path is easy too.

for u in topological_order:
    for v, w in adj[u]:
        dist[v] = min(dist[v], dist[u] + w)      # or max, for longest path

Longest path is NP-hard on general digraphs and O(V + E) here.

Interview trap. Longest path is NP-hard on general graphs but easy on acyclic ones, and conflating the two cases produces either an unnecessary heuristic or an incorrect one.

Engineering practice. Check acyclicity, then relax in topological order, and note that the same pass gives both extremes.

the second-shortest path

The second-shortest route is definition-sensitive: allowing repeated vertices gives a different problem from finding the second distinct simple path.

Two-distance Dijkstra handles non-negative walks; Yen's algorithm enumerates loopless paths, while deleting each edge of the shortest simple path and rerunning can find the second distinct simple path but costs one shortest-path run per edge.

Choose the algorithm only after defining what counts as the second route.

# Non-negative walks: maintain best[u] and second[u] during relaxation.
# Loopless paths: Yen's algorithm generates deviations from the prior path.
# For only the second distinct simple path, deleting each edge of the shortest
# path and taking the cheapest rerun is valid, but needs O(path_length) runs.

Interview trap. Quoting one method without defining whether paths may repeat vertices or whether equal-cost alternatives count as distinct makes the result ambiguous.

Engineering practice. Define the path semantics first, then use two-distance relaxation for walks or a loopless k-shortest-path method when simplicity is required.

graphs that do not fit in memory

At web scale the adjacency structure exceeds memory, and the algorithms change to streaming or partitioned forms.

Vertex-centric models process a partition at a time with message passing between supersteps, trading round trips for memory.

The frontier is usually what breaks first.

# 10^9-edge graph: adjacency in CSR ≈ 8 GB.
# A BFS frontier across the widest cut can exceed 10^8 vertices at once.
# Vertex-centric supersteps trade round trips for memory.

Interview trap. Assuming an in-memory algorithm ports directly to a distributed setting ignores that the frontier, not the graph, is often what does not fit.

Engineering practice. Estimate both the graph and the frontier, and choose an external or distributed formulation when either exceeds the budget.

dynamic connectivity

Union-find handles additions but not deletions, so a workload with edge removals needs a different structure.

Offline dynamic connectivity processes the whole query sequence with a segment tree over time and a rollback-capable disjoint-set structure.

Rollback needs union by rank without path compression.

# Path compression rewrites parents during find(), destroying the information
# an undo would need. Keep rank-only union, accept O(log n), and store an
# explicit stack of (child, old_rank) to roll back.

Interview trap. Attempting to undo a union with path compression corrupts the structure, since compression discards the information needed to roll back.

Engineering practice. Use union by rank without path compression when rollback is required, and accept the logarithmic bound that follows.

problem reductions

Much of advanced graph work is recognising that a problem reduces to a known one rather than inventing an algorithm.

Scheduling with dependencies is topological sorting, resource assignment is bipartite matching, and reliability questions are often minimum cuts.

Most of the work is recognising the standard problem.

Problem	Reduces to
Task scheduling with dependencies	topological sort
Assigning shifts to staff	bipartite matching
Minimum links to disconnect a network	min cut
Cheapest way to connect all sites	minimum spanning tree

Interview trap. Designing a bespoke greedy algorithm for a problem with a known reduction usually produces something both slower and wrong on an edge case.

Engineering practice. Search for the reduction first, and state the mapping between the problem's objects and the standard formulation.

verifying graph algorithms

Advanced graph algorithms are best verified against a slow reference implementation on small random graphs.

Random graphs of five to ten vertices, compared against brute force, expose the low-link, residual-edge, and loop-order defects that hand-picked examples miss.

Random small graphs against brute force finds the loop-order bugs.

for _ in range(10_000):
    g = random_graph(n=random.randint(1, 7))
    assert floyd_warshall(g) == brute_force_all_pairs(g)

A wrong Floyd-Warshall loop order survives hand-picked examples and dies here in seconds.

Interview trap. Testing on a few drawn examples is how a wrong loop order in Floyd-Warshall survives into production.

Engineering practice. Write the brute-force reference first, and run randomised comparison over thousands of small graphs.

knowing when to stop

Recognising that a problem is NP-hard is a complete answer, and continuing to search for a polynomial algorithm is the wrong response.

The productive next step is to bound the instance size, find an approximation with a proven ratio, or exploit a structural property such as acyclicity or bounded treewidth.

Name the hardness, then give the bound and the approximation.

# "This is NP-hard. For n <= 20 I would use the O(2^n n^2) DP.
#  Beyond that, Christofides gives a 1.5-approximation on metric instances,
#  and I would report the ratio rather than call the result optimal."

Interview trap. Presenting an exponential algorithm as though it were polynomial, or an unbounded heuristic as though it were an approximation, misrepresents the result.

Engineering practice. Name the hardness, then propose the exact method for small instances and the approximation with its ratio for large ones.