Minimum spanning trees and network flow

In short

A minimum spanning tree (MST) is the cheapest set of edges that keeps every vertex of a connected weighted undirected graph in one piece, and network flow asks how much material can be pushed from a source to a sink through capacitated directed edges. Both are the "heavy" end of the undergraduate algorithms syllabus: MST is examined through Kruskal, Prim, union-find and the cut/cycle properties, and flow through Ford-Fulkerson, Edmonds-Karp, Dinic and the max-flow min-cut theorem. GATE CS asks 1-2 marks on MST almost every year (uniqueness, edge-weight changes, running times) and flow appears as min-cut, bipartite matching or a modelling question. In Indian hiring, MST and union-find are standard in online rounds at Amazon, Google, Microsoft, Flipkart, Zoho, Samsung R&D and Media.net, while flow modelling turns up in design rounds at quant firms and in competitive-programming-screened roles.

Explained

Spanning trees and the two structural properties

• A spanning tree of a connected graph with V vertices and E edges has exactly V − 1 edges, touches every vertex, and has no cycle. Removing any edge disconnects it; adding any edge creates exactly one cycle.
• An MST is a spanning tree of minimum total edge weight. A disconnected graph has no spanning tree - only a minimum spanning forest, one tree per component.
• Cut property (the basis of Prim): for any cut (partition of vertices into S and V−S), the lightest edge crossing the cut belongs to some MST. If it is strictly lightest, it belongs to every MST.
• Cycle property (the basis of Kruskal's rejections): for any cycle, the heaviest edge on that cycle can be left out of some MST. If it is strictly heaviest, no MST contains it.
• Both are proved by exchange argument: assume an MST T lacking the light cut edge e; adding e makes a cycle containing another crossing edge f with w(f) ≥ w(e); T + e − f is a spanning tree no heavier, so an MST contains e.
• Uniqueness: if all edge weights are distinct, the MST is unique. Equal weights can give several MSTs, but every MST has the same multiset of edge weights, hence the same total cost.
• Not shortest paths: the MST path between two vertices need not be the shortest path. MST minimises total weight, Dijkstra minimises per-destination distance.
• Minimax property: the MST path between u and v minimises the maximum edge weight on the path (the bottleneck path) - the basis of many "minimise the largest hop" questions.
• MST is invariant under any monotone increasing transform of weights (add a constant, multiply by a positive constant, take logs) because only the ordering matters.

Kruskal's algorithm - sort edges, union-find

1. Sort all E edges by weight, ascending.
2. Initialise a disjoint-set structure with V singleton sets.
3. Scan edges in order; accept edge (u, v) if find(u) != find(v) (it joins two different components), then union(u, v); else reject it as cycle-forming.
4. Stop after V − 1 accepted edges (or when edges run out - then the graph was disconnected, giving a forest).
5. Complexity: O(E log E) for the sort, plus O(E α(V)) for the set operations, where α is the inverse Ackermann function (≤ 5 in practice). Overall O(E log E) = O(E log V).
6. Disjoint-set union (DSU) with two optimisations: union by rank/size (attach the smaller tree under the larger) and path compression (point every node visited by find straight at the root). Together they give near-constant amortised cost.
7. Greedy and edge-based; naturally handles sparse graphs and pre-sorted or integer weights (counting/radix sort makes it O(E α(V)) when weights are small integers).
8. Variant: process edges in descending order and delete an edge if the graph stays connected without it - the reverse-delete algorithm, correct but slower.

Prim's algorithm - grow one tree

1. Pick any start vertex r; set key[r] = 0, key[v] = ∞ for others, parent[v] = NIL.
2. Repeatedly extract the non-tree vertex with the smallest key and add it (with its parent edge) to the tree.
3. For every neighbour v of the newly added u that is still outside the tree, if w(u, v) < key[v], set key[v] = w(u, v) and parent[v] = u (decrease-key).
4. After V extractions the parent array is the MST.
5. Complexity: adjacency matrix + array of keys → O(V²); adjacency list + binary heap → O(E log V); Fibonacci heap → O(E + V log V) (theoretically best, rarely coded).
6. Choose Prim with a matrix/array for dense graphs (E ≈ V²), Kruskal for sparse graphs; for E ≈ V² Prim's O(V²) beats Kruskal's O(V² log V).
7. Prim keeps one connected tree at all times; Kruskal keeps a forest that merges. Prim resembles Dijkstra in shape - the only change is that the key stores the edge weight w(u, v), not the path sum d[u] + w(u, v).
8. Prim on a disconnected graph finds the MST of only the start vertex's component; restart from each unvisited vertex for a forest.

Boruvka, special cases and MST variants

• Boruvka (Sollin): each round, every component picks its own cheapest outgoing edge and all are added simultaneously; components at least halve each round, so O(E log V) in O(log V) rounds. Being round-based, it is the natural parallel/distributed MST algorithm (also the base of linear-time randomised MST).
• Ties in Boruvka must be broken consistently (e.g. by edge index) or simultaneous choices can form a cycle.
• Maximum spanning tree: negate the weights (or sort descending in Kruskal) - same algorithms.
• Second-best MST: build the MST, then for every non-tree edge e = (u, v) compute the maximum tree-edge weight on the tree path u→v and take the smallest value of w(e) − maxpath; O(VE) naively, O(E log V) with LCA/binary lifting.
• Minimum bottleneck spanning tree: every MST is one, but the converse is false.
• MST with one edge forced in: contract it (or start Kruskal with it accepted). Forced out: delete it and rebuild.
• Edge-weight update: if a tree edge's weight decreases, the MST is unchanged; if a non-tree edge's weight drops below the heaviest edge on its tree path, swap them.
• Degree-constrained MST, Steiner tree (connect a subset of terminals, extra vertices allowed) and bounded-diameter MST (cheapest tree of diameter ≤ k) are NP-hard - a standard exam trap: plain MST is polynomial, these constrained cousins are not. The *unconstrained* minimum-diameter spanning tree is polynomial (Hassin-Tamir, via the absolute 1-centre).
• Euclidean MST of n points in a plane is a subgraph of the Delaunay triangulation, giving O(n log n). The MST also provides the classic 2-approximation for metric TSP (double the MST and shortcut the Euler tour).

Flow networks, Ford-Fulkerson and Edmonds-Karp

• A flow network is a directed graph G = (V, E) with capacity c(u, v) ≥ 0, a source s and a sink t. A flow f satisfies capacity constraints 0 ≤ f(u, v) ≤ c(u, v) and conservation (inflow = outflow) at every vertex other than s and t.
• Value of the flow |f| = net flow out of s = net flow into t. Maximum flow maximises |f|.
• Residual graph G_f: forward residual capacity c(u,v) − f(u,v), plus a backward edge of capacity f(u, v) that allows cancelling earlier flow. Backward edges are what make the greedy correct.
• Augmenting path: an s→t path in G_f; push along it the bottleneck = minimum residual capacity on the path.
• Ford-Fulkerson method: while an augmenting path exists, augment. With integer capacities it terminates in at most |f*| augmentations → O(E · |f*|), which is not polynomial in the input size (the classic 4-vertex, 5-edge graph with outer capacities 1,000,000 and a middle edge of 1 can take 2,000,000 iterations if paths are chosen badly). With irrational capacities it may not terminate at all.
• Edmonds-Karp: Ford-Fulkerson choosing the shortest augmenting path by BFS (fewest edges). Each augmentation saturates at least one edge and distances never decrease → at most O(VE) augmentations → O(VE²), independent of capacities.
• Dinic's algorithm: build a level graph by BFS, then find a blocking flow by DFS in that graph; repeat. O(V²E) general, O(E√E) on unit-capacity graphs, and O(E√V) when unit capacities also bound each vertex (bipartite matching) - the practical choice for contests.
• Push-relabel (Goldberg-Tarjan) works with preflows and heights: O(V³) with the FIFO rule, O(V²√E) with the highest-label rule; fastest in some dense implementations.
• Integrality theorem: with integer capacities there exists an integer maximum flow - so flow can model combinatorial selection problems.

Max-flow min-cut and modelling

• An s-t cut (S, T) splits V with s ∈ S, t ∈ T. Its capacity is the sum of capacities of edges from S to T only (edges T→S are not counted).
• Max-flow min-cut theorem: the value of a maximum flow equals the capacity of a minimum s-t cut. Equivalent statements: f is maximum ⇔ G_f has no augmenting path ⇔ |f| equals some cut's capacity.
• Recovering the min cut: after max flow, run BFS/DFS in the residual graph from s; S = reachable set, T = the rest. The S→T edges are saturated, and the backward T→S edges carry zero flow; the saturated S→T edges form the min cut.
• Weak duality is easy (any flow ≤ any cut, since all flow must cross); the theorem is the LP duality of the flow LP and is the standard proof-type question.
• Standard reductions:
  • Multiple sources/sinks: add a super-source with ∞ edges to all sources, a super-sink from all sinks.
  • Vertex capacities: split v into v_in → v_out with capacity = vertex capacity.
  • Undirected edge of capacity c: two opposite directed edges of capacity c each.
  • Edge-disjoint paths (Menger's theorem): set every capacity to 1; max flow = maximum number of edge-disjoint s-t paths = minimum edges to delete to disconnect s from t. Vertex-disjoint: also split vertices.
  • Bipartite matching: s → left (cap 1), left → right edges (cap 1), right → t (cap 1); max flow = maximum matching. Hopcroft-Karp does the same in O(E√V).
  • Konig's theorem (bipartite): max matching = min vertex cover; and max independent set = V − max matching.
  • Project selection / max-closure, image segmentation and baseball elimination are classic min-cut models.
  • Lower bounds on edges, circulation with demands: transform to a flow problem with excess/deficit super-nodes.
• Min-cost max-flow (MCMF): each edge also has a cost per unit; find a maximum flow of minimum total cost using successive shortest augmenting paths with Bellman-Ford/SPFA, or Johnson potentials + Dijkstra to handle the negative residual costs. Used for assignment/transportation problems; the Hungarian algorithm is the specialised O(n³) assignment method.
• Limitation: negative capacities are meaningless; flow is for *capacitated* throughput, not for minimising path length, and MCMF with negative cycles needs cycle cancelling first.

Key points

• Spanning tree - acyclic connected subgraph with all V vertices and exactly V − 1 edges.
• Cut property - the lightest edge across any cut is in some MST; strictly lightest ⇒ in every MST.
• Cycle property - the heaviest edge on any cycle is excludable; strictly heaviest ⇒ in no MST.
• Uniqueness - distinct weights ⇒ unique MST; equal weights ⇒ possibly many MSTs but identical total weight and identical weight multiset.
• Kruskal - sort edges + DSU, O(E log E); edge-based, best for sparse graphs, yields a forest if disconnected.
• DSU with union by rank + path compression - amortised O(α(V)) per operation, effectively constant.
• Prim - grow one tree with a priority queue, O(E log V) with a binary heap, O(V²) with an array (better for dense graphs).
• Boruvka - O(log V) parallel rounds, each component adds its cheapest outgoing edge; needs consistent tie-breaking.
• MST ≠ shortest path tree, but the MST path is the minimum bottleneck path between any two vertices.
• NP-hard MST variants - degree-constrained MST, Steiner tree, bounded-diameter MST (plain minimum-diameter spanning tree is polynomial).
• Flow conservation - inflow = outflow at all vertices except s and t; 0 ≤ f(e) ≤ c(e).
• Residual graph and backward edges - allow undoing earlier flow; without them greedy augmentation is wrong.
• Ford-Fulkerson - O(E·|f*|), depends on capacity values; Edmonds-Karp (BFS) is O(VE²); Dinic is O(V²E), O(E√E) for unit capacities and O(E√V) for bipartite matching.
• Max-flow min-cut theorem - max |f| = min s-t cut capacity; the cut is read off by residual reachability from s.
• Integrality theorem - integer capacities admit an integer max flow, so flow solves selection and matching problems.
• Bipartite matching via flow - unit capacities; max matching = min vertex cover (Konig) and independent set = V − matching.
• Menger's theorem - max edge-disjoint s-t paths = min s-t edge cut (unit capacities).
• Min-cost max-flow - successive shortest paths with potentials; solves assignment and transportation problems.

Formulas and examples

Units: edge weights carry whatever the model uses - kilometres of cable, rupees of cost, Mbps of bandwidth, litres/second; capacities and flows share the same unit; costs in MCMF are rupees per unit of flow.

Example 1 - Kruskal by hand with the rejection trace. Graph on 6 vertices (A-F), edges: AB 4, AC 3, BC 1, BD 2, CD 4, CE 2, DE 3, DF 2, EF 3.

MST edges = {BC, BD, CE, DF, AC}, count = 5 = V − 1. Total cost = 1 + 2 + 2 + 2 + 3 = 10.

Example 2 - Prim from A on the same graph.

• Start A: key(B) = 4, key(C) = 3 → extract C (3), edge AC.
• Update from C: key(B) = min(4, 1) = 1, key(D) = 4, key(E) = 2 → extract B (1), edge CB.
• Update from B: key(D) = min(4, 2) = 2 → extract D (2) (tie with E, either order), edge BD.
• Update from D: key(E) = min(2, 3) = 2, key(F) = 2 → extract E (2), edge CE; then F (2), edge DF.
• Tree = {AC, CB, BD, CE, DF}, cost = 3 + 1 + 2 + 2 + 2 = 10 - same cost as Kruskal, as it must be. (Here the edge set is identical too; with ties the sets can differ while the cost cannot.)

Example 3 - Ford-Fulkerson and the min cut. Network: s→A 10, s→B 10, A→B 2, A→t 4, B→t 10. (Capacities in Mbps.)

• Augment s→B→t: bottleneck min(10, 10) = 10. Residual: s→B 0, B→t 0, back-edges B→s 10, t→B 10.
• Augment s→A→t: bottleneck min(10, 4) = 4. Residual: A→t 0, s→A 6.
• Any further path? s→A has 6 left, but from A only A→B (2) and A→t (0) remain; A→B→t needs B→t, which is saturated. No augmenting path. Max flow = 14 Mbps.
• Min cut by residual reachability from s: reachable = {s, A, B} (s→A has 6 spare, A→B has 2 spare), so S = {s, A, B}, T = {t}. Cut edges A→t (4) and B→t (10) → capacity = 14 = max flow. ✔

Example 4 - Edmonds-Karp beats bad path choices. Network: s→v 1000, s→w 1000, v→w 1, v→t 1000, w→t 1000.

• Naive Ford-Fulkerson picking s→v→w→t augments 1 unit, then s→w→v→t (back edge) 1 unit, and so on - up to 2,000 augmentations.
• Edmonds-Karp uses BFS, so it picks the 2-edge paths s→v→t (1000) and s→w→t (1000) first: 2 augmentations, max flow = 2000. The min cut is {s→v, s→w} = 2000.

Example 5 - Bipartite matching by flow (campus placement allocation). 4 students S1-S4, 4 interview slots L1-L4. Preferences: S1:{L1,L2}, S2:{L1}, S3:{L2,L3}, S4:{L3,L4}.

• Build s→Si cap 1, Si→Lj cap 1 for each preference, Lj→t cap 1. Max flow = max matching.
• Augment s→S2→L1→t (1); s→S1→L2→t (1); s→S3→L3→t (1); s→S4→L4→t (1). Flow = 4 → a perfect matching S2-L1, S1-L2, S3-L3, S4-L4.
• Cross-check by Konig: min vertex cover must also be 4, and max independent set = 8 − 4 = 4.

Algorithm choice table

# Kruskal with DSU (union by size + path compression)
def kruskal(n, edges):                      # edges: list of (w, u, v)
    parent = list(range(n)); size = [1]*n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x
    cost, chosen = 0, []
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru == rv:                        # cycle -> reject (cycle property)
            continue
        if size[ru] < size[rv]: ru, rv = rv, ru
        parent[rv] = ru; size[ru] += size[rv]
        cost += w; chosen.append((u, v, w))
        if len(chosen) == n - 1: break
    return (cost, chosen) if len(chosen) == n - 1 else (None, chosen)  # None => forest

from collections import deque
# Edmonds-Karp: BFS augmenting paths on an adjacency-matrix residual graph
def max_flow(cap, s, t):                    # cap[u][v] = capacity, modified in place
    n, total = len(cap), 0
    while True:
        par = [-1]*n; par[s] = s; q = deque([s])
        while q and par[t] == -1:
            u = q.popleft()
            for v in range(n):
                if par[v] == -1 and cap[u][v] > 0:
                    par[v] = u; q.append(v)
        if par[t] == -1:                    # no augmenting path -> max flow reached
            return total
        v, bott = t, float('inf')
        while v != s:                       # bottleneck on the path
            bott = min(bott, cap[par[v]][v]); v = par[v]
        v = t
        while v != s:                       # push flow, add residual back-edge
            cap[par[v]][v] -= bott; cap[v][par[v]] += bott; v = par[v]
        total += bott

Where it is used

• Telecom and ISP network planning: BSNL, Reliance Jio and Airtel use MST-style models to lay the cheapest fibre backbone between exchanges, and flow/min-cut to size bandwidth and find bottleneck links; BharatNet gram-panchayat connectivity is a textbook MST/Steiner problem.
• Power transmission and utilities: POWERGRID and state transcos plan radial distribution feeders (a spanning tree by design, since distribution networks are run radially) and use flow models for load transfer; water and gas pipeline sizing uses capacitated flow.
• Logistics, railways and ride-hailing: Indian Railways freight routing, Delhivery/Blue Dart hub linking and Ola/Uber driver-rider assignment are min-cost-flow and matching problems; airline crew pairing uses flow with side constraints.
• Clustering and ML: single-linkage clustering is exactly MST plus cutting the k−1 heaviest edges; image segmentation uses graph min-cut (the Boykov-Jolly model); MST-based outlier detection in analytics teams.
• Scheduling and allocation software: campus placement slot allocation, hospital-resident matching, exam seat and invigilator assignment, and course registration solved by bipartite matching / flow with capacities.
• Job roles and interviews: SDE roles at Amazon, Google, Microsoft, Flipkart, Zoho, Samsung R&D, Media.net and quant/HFT firms ask union-find and MST routinely; flow and min-cut show up in competitive-programming-screened hiring (ICPC/Codeforces background) and in network-planning and OR roles at TCS Research, Mu Sigma and the DRDO/ISRO software groups.

Interview questions

• Q: Why does Kruskal's greedy choice give an optimal MST? A: By the cut property - the lightest edge joining two different components is safe for some MST - and an exchange argument shows swapping it into any MST never increases the cost.
• Q: When would you prefer Prim over Kruskal? A: On dense graphs given as an adjacency matrix, where Prim with a simple key array runs in O(V²) versus Kruskal's O(E log E) ≈ O(V² log V); Prim also suits a growing-tree/online setting.
• Q: Is the MST unique? A: Yes if all edge weights are distinct; with duplicate weights there may be several MSTs, but all have the same total weight and the same multiset of edge weights.
• Q: If every edge weight is increased by 10, does the MST change? A: The edge set does not change (only the ordering matters, and every spanning tree gains exactly 10(V−1)), but the total cost increases by 10(V−1). Shortest paths *can* change, since paths have different edge counts.
• Q: Is the MST also a shortest-path tree? A: No. It minimises total weight, not individual distances; however the MST path between two vertices does minimise the maximum edge weight on the path.
• Q: How do you find the second-best MST? A: Build the MST, then for each non-tree edge compute the heaviest tree edge on the path between its endpoints and take the minimum of w(e) − that weight; add e and remove that edge.
• Q: Why does Ford-Fulkerson need residual back edges? A: They let later augmentations cancel flow pushed along a bad earlier route; without them the method can stop at a non-optimal flow.
• Q: Why is Ford-Fulkerson not polynomial, and how does Edmonds-Karp fix it? A: Its O(E·|f*|) bound depends on the capacity values, which can be exponential in the input bit-length; BFS (shortest augmenting path) bounds augmentations at O(VE), giving O(VE²) independent of capacities.
• Q: State and explain max-flow min-cut. A: The maximum s-t flow equals the minimum s-t cut capacity; any flow must cross every cut (weak duality), and when no augmenting path exists the set reachable from s in the residual graph defines a cut whose edges are all saturated.
• Q: How do you extract the actual minimum cut after computing max flow? A: BFS/DFS from s in the residual graph; the reachable vertices form S, the rest T, and the saturated S→T edges are the min cut.
• Q: How does maximum bipartite matching reduce to max flow? A: Add a source to all left vertices and a sink from all right vertices with unit capacities and unit-capacity matching edges; the integral max flow equals the maximum matching, and Dinic runs in O(E√V).
• Q: Can Dijkstra be used inside min-cost max-flow? A: Not directly, because residual edges have negative costs; with Johnson-style potentials the reduced costs become non-negative and Dijkstra works for each successive shortest path.
• Q: Which MST-like problems are NP-hard? A: Degree-constrained MST, Steiner tree (connecting a terminal subset), bounded-diameter and bounded-hop MST variants - adding constraints destroys the matroid/greedy structure. The unconstrained minimum-diameter spanning tree, by contrast, is polynomial.

Common mistakes

• Treating the MST as a shortest-path tree, or running Dijkstra's relaxation d[u] + w instead of Prim's w(u,v) as the key.
• Forgetting to check connectivity: Kruskal silently returns a forest with fewer than V − 1 edges, which must be reported, not summed as an MST.
• Writing DSU without path compression or union by rank, turning O(α) into O(V) per find and timing out on 10⁵-edge inputs.
• Omitting residual back edges (or forgetting to add capacity to the reverse edge) in max-flow code - the answer looks plausible but is too small.
• Counting T→S edges in a cut's capacity; only the S→T capacities count, and the flow on T→S edges is irrelevant to the cut value.
• Claiming Ford-Fulkerson is O(E·V) or polynomial, or hand-tracing it with DFS and reporting the first saturating flow as maximum without rechecking for augmenting paths.
• Using max flow where min-cost flow is needed (a maximum flow is rarely the cheapest one), or assuming a unique min cut when several can have equal capacity.
• Applying flow algorithms to undirected graphs without replacing each edge by two opposing directed edges, or ignoring vertex capacities instead of splitting the vertex.

Related topics

Graph algorithms: BFS, DFS and shortest paths · Greedy algorithms · Divide and conquer · Dynamic programming · Time and space complexity · DSA interview patterns