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

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

Asked at: Apple Interview Guide

Asked at: Coinbase Interview Guide

Asked at: Databricks Interview Guide