# Minimum Spanning Tree Interview Patterns: Kruskal, Prim, and Network Design Problems (2025)

Source: https://www.techinterview.org/post/3233465237/minimum-spanning-tree-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## What Is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) of a weighted undirected graph is a spanning tree (connects all V vertices) with the minimum total edge weight. Properties: always has exactly V-1 edges. May not be unique (if edge weights are equal). Cut property: the minimum weight edge crossing any cut is in some MST. Cycle property: the maximum weight edge in any cycle is not in any MST. Used for: network design (connect cities with minimum cable length), cluster analysis, image segmentation, approximation of TSP.

## Kruskal Algorithm

Sort edges by weight. Use Union-Find to avoid cycles. For each edge (u,v,w) in sorted order: if find(u) != find(v): add to MST, union(u,v). Stop when V-1 edges are added. O(E log E) for sorting + O(E alpha(V)) for Union-Find = O(E log E). Preferred for sparse graphs (E close to V). Easy to implement with sorted edge list.


```
def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return False
        parent[rx] = ry; return True
    cost = 0
    for u, v, w in edges:
        if union(u, v):
            cost += w
    return cost
```


## Prim Algorithm

Greedy: grow the MST from a starting vertex. Priority queue of (weight, vertex). Initialize with (0, start). While queue: pop (w, u). If u is visited: skip. Mark visited, add w to MST cost. For each neighbor v of u: if not visited: push (weight(u,v), v). O((V+E) log V) with a binary heap. Preferred for dense graphs (adjacency matrix representation: O(V^2)). Conceptually similar to Dijkstra (replace distance with edge weight).


```
import heapq
def prim(graph, n):
    visited = set()
    heap = [(0, 0)]  # (weight, node)
    cost = 0
    while heap and len(visited) < n:
        w, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        cost += w
        for v, weight in graph[u]:
            if v not in visited:
                heapq.heappush(heap, (weight, v))
    return cost
```


## Maximum Spanning Tree

Find the spanning tree with maximum total weight. Two approaches: (1) Negate all edge weights, run Kruskal for MST, negate the result. (2) Run Kruskal in decreasing weight order (select the heaviest edge that does not form a cycle). Use cases: maximize reliability in a network (where edge weight = reliability), find the bottleneck spanning tree (max minimum-weight path between all pairs).

## Common Interview Problems

- LC 1584 Min Cost to Connect All Points: MST on a complete graph (Prim with O(V^2) is optimal for dense graphs).

- LC 1135 Connecting Cities With Minimum Cost: Kruskal, same as classic MST.

- LC 1168 Optimize Water Distribution in a Village: add a virtual node for wells, run MST.

- LC 1489 Find Critical and Pseudo-Critical Edges: for each edge, check if it is in all MSTs (critical) or some MSTs (pseudo-critical).

- Second MST: remove each MST edge one at a time, find the min replacement edge -- O(E^2).

## Kruskal vs Prim

Kruskal: processes edges globally sorted by weight. Better for sparse graphs. Requires sorting (O(E log E)). Prim: grows from a vertex, processes neighbors. Better for dense graphs (O(V^2) with matrix). Both give the same MST result. In practice: Kruskal with Union-Find is simpler to code in interviews and covers most cases. Use Prim when given an adjacency matrix or when the graph is nearly complete (E close to V^2).

Asked at: [Meta Interview Guide](https://techinterview.org/meta-interview/)

Asked at: [Apple Interview Guide](https://techinterview.org/apple-interview/)

Asked at: [Coinbase Interview Guide](https://techinterview.org/coinbase-interview/)

Asked at: [Databricks Interview Guide](https://techinterview.org/databricks-interview/)