Minimum Spanning Tree: Prim's and Kruskal's Algorithms

A Minimum Spanning Tree (MST) of a connected, weighted, undirected graph is a subset of edges that connects all V vertices with no cycle and the smallest possible total weight. It always uses exactly V - 1 edges. MSTs answer “what’s the cheapest way to wire up every node?” — network design, clustering, road/cable layout. Two greedy algorithms find it: Prim’s grows a tree outward, Kruskal’s adds the cheapest safe edges globally.

Prim’s algorithm (grow with a min-heap)

Prim’s starts from any vertex and repeatedly adds the cheapest edge that reaches a new vertex, using a priority queue keyed by edge weight — structurally similar to Dijkstra.

#include <vector>
#include <queue>

// graph[u] = list of (neighbor, weight); returns total MST weight
long long primMST(const std::vector<std::vector<std::pair<int,int>>>& graph) {
    int n = graph.size();
    std::vector<bool> inMST(n, false);
    using P = std::pair<int,int>;                  // (weight, vertex)
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    pq.push({0, 0});
    long long total = 0; int taken = 0;
    while (!pq.empty() && taken < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;                    // skip settled vertex
        inMST[u] = true; total += w; taken++;
        for (auto [v, wt] : graph[u])
            if (!inMST[v]) pq.push({wt, v});
    }
    return total;
}

// graph.get(u) = list of int[]{neighbor, weight}; returns total MST weight
long primMST(List<List<int[]>> graph) {
    int n = graph.size();
    boolean[] inMST = new boolean[n];
    // min-heap of int[]{weight, vertex}
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.add(new int[]{0, 0});
    long total = 0; int taken = 0;
    while (!pq.isEmpty() && taken < n) {
        int[] top = pq.poll();
        int w = top[0], u = top[1];
        if (inMST[u]) continue;                    // skip settled vertex
        inMST[u] = true; total += w; taken++;
        for (int[] e : graph.get(u))
            if (!inMST[e[0]]) pq.add(new int[]{e[1], e[0]});
    }
    return total;
}

// graph[u] = array of [neighbor, weight]; returns total MST weight
function primMST(graph) {
  const n = graph.length;
  const inMST = new Array(n).fill(false);
  const heap = [[0, 0]];                            // [weight, vertex]
  const push = (x) => {
    heap.push(x); let i = heap.length - 1;
    while (i > 0) { const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]]; i = p; }
  };
  const pop = () => {
    const top = heap[0], last = heap.pop();
    if (heap.length) { heap[0] = last; let i = 0;
      while (true) { let s = i, l = 2*i+1, r = 2*i+2;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[i], heap[s]] = [heap[s], heap[i]]; i = s; } }
    return top;
  };
  let total = 0, taken = 0;
  while (heap.length && taken < n) {
    const [w, u] = pop();
    if (inMST[u]) continue;                         // skip settled vertex
    inMST[u] = true; total += w; taken++;
    for (const [v, wt] of graph[u])
      if (!inMST[v]) push([wt, v]);
  }
  return total;
}

import heapq

# graph[u] = list of (neighbor, weight); returns total MST weight
def prim_mst(graph):
    n = len(graph)
    in_mst = [False] * n
    pq = [(0, 0)]                                   # (weight, vertex)
    total = taken = 0
    while pq and taken < n:
        w, u = heapq.heappop(pq)
        if in_mst[u]:                               # skip settled vertex
            continue
        in_mst[u] = True
        total += w
        taken += 1
        for v, wt in graph[u]:
            if not in_mst[v]:
                heapq.heappush(pq, (wt, v))
    return total

Pitfall: A vertex can sit in the heap multiple times with different weights. Check inMST[u] right after popping and skip if already included — otherwise you double-count.

Kruskal’s algorithm (sort edges + union-find)

Kruskal’s takes the opposite view: sort all edges by weight, then add each edge whose endpoints aren’t already connected. “Already connected?” is answered in near-constant time by union-find. Adding an edge within the same set would create a cycle, so it’s skipped.

struct DSU {
    std::vector<int> p, r;
    DSU(int n): p(n), r(n, 0) { for (int i=0;i<n;i++) p[i]=i; }
    int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
    bool unite(int a,int b){ a=find(a); b=find(b);
        if(a==b) return false;
        if(r[a]<r[b]) std::swap(a,b);
        p[b]=a; if(r[a]==r[b]) r[a]++; return true; }
};
// edges: (weight, u, v); returns total MST weight
long long kruskalMST(int V, std::vector<std::array<int,3>> edges) {
    std::sort(edges.begin(), edges.end());         // by weight (index 0)
    DSU dsu(V);
    long long total = 0; int taken = 0;
    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) { total += w; if (++taken == V-1) break; }
    }
    return total;
}

class DSU {
    int[] p, r;
    DSU(int n){ p=new int[n]; r=new int[n]; for(int i=0;i<n;i++) p[i]=i; }
    int find(int x){ return p[x]==x ? x : (p[x]=find(p[x])); }
    boolean unite(int a,int b){ a=find(a); b=find(b);
        if(a==b) return false;
        if(r[a]<r[b]){ int t=a; a=b; b=t; }
        p[b]=a; if(r[a]==r[b]) r[a]++; return true; }
}
// edges: int[]{weight, u, v}; returns total MST weight
long kruskalMST(int V, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[0] - b[0]);      // by weight
    DSU dsu = new DSU(V);
    long total = 0; int taken = 0;
    for (int[] e : edges)
        if (dsu.unite(e[1], e[2])) {
            total += e[0];
            if (++taken == V - 1) break;
        }
    return total;
}

// edges: array of [weight, u, v]; returns total MST weight
function kruskalMST(V, edges) {
  const parent = Array.from({ length: V }, (_, i) => i);
  const rank = new Array(V).fill(0);
  const find = (x) => parent[x] === x ? x : (parent[x] = find(parent[x]));
  const unite = (a, b) => {
    a = find(a); b = find(b);
    if (a === b) return false;
    if (rank[a] < rank[b]) [a, b] = [b, a];
    parent[b] = a;
    if (rank[a] === rank[b]) rank[a]++;
    return true;
  };
  edges.sort((x, y) => x[0] - y[0]);                // by weight
  let total = 0, taken = 0;
  for (const [w, u, v] of edges)
    if (unite(u, v)) { total += w; if (++taken === V - 1) break; }
  return total;
}

# edges: list of (weight, u, v); returns total MST weight
def kruskal_mst(V, edges):
    parent = list(range(V))
    rank = [0] * V
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def unite(a, b):
        a, b = find(a), find(b)
        if a == b:
            return False
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]:
            rank[a] += 1
        return True
    edges.sort(key=lambda e: e[0])                  # by weight
    total = taken = 0
    for w, u, v in edges:
        if unite(u, v):
            total += w
            taken += 1
            if taken == V - 1:
                break
    return total

Complexity and choosing one

Algorithm   Time                  Best for
Prim's      O((V + E) log V)      dense graphs (adjacency list + heap)
Kruskal's   O(E log E)            sparse graphs / edge list

Both produce a tree of the same total weight (the MST weight is unique when edge weights are distinct). Pick Prim’s when the graph is given as an adjacency list and is dense; pick Kruskal’s when you have an edge list or the graph is sparse — and it leans entirely on union-find.

Ready to test yourself? Head to the graph exercises.