SyntaxPilot
Courses/DSA and Coding Problems/Lesson 56
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 56 of 90

Minimum spanning tree: Kruskal and Prim

queued

These are the notes for DSA episode 56. Episode 55's Union-Find told us when a cable is wasted. Today we connect every office for the least total cable: the minimum spanning tree (MST). We start from a real-life problem (cabling offices in a grid city), define every word, try the obvious idea (every set of n - 1 cables: correct, but Time Limit Exceeded on only 12 offices), fall into a greedy trap (the n - 1 cheapest cables give 18 instead of 20), find the key insight (the cheapest cable that joins two separate groups is always safe: the cut property), and finish with Kruskal (sort + Union-Find, O(E log E)) and Prim (grow one tree, O(V²) for dense graphs). Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

The telecom company must connect all its offices in a grid city laid out in sectors, like Chandigarh. Cables can't cut through buildings, so they run along streets: so far east or west, then so far north or south. Every office must be connected to every other (directly or through other offices), and every metre costs money.

With the cables In code
An office at grid position (x, y) a point points[i] = [x, y]
A possible cable between two offices an edge between every pair
Cable length along streets Manhattan distance |x1 - x2| + |y1 - y2|
A plan that connects everyone, no wasted cable a spanning tree
The cheapest such plan the minimum spanning tree

Every word, from zero

  • Tree: a connected graph with no cycle. A tree on n nodes has exactly n - 1 edges: fewer can't connect everyone, more must make a cycle.
  • Spanning tree: a set of edges that connects all n nodes with no cycle.
  • Minimum spanning tree (MST): the spanning tree with the smallest total weight. (There can be several with the same total.)
  • Manhattan distance: |x1 - x2| + |y1 - y2|, the distance along a street grid (named after Manhattan's grid).
  • Absolute value |x|: x without its sign; Java Math.abs.
  • Greedy: always take the choice that looks best right now; it's only correct when you can prove it.
  • Cut: a split of the nodes into two sides. A crossing edge has one end on each side.
  • Cut property: the cheapest edge crossing any cut belongs to some MST.
  • Kruskal's algorithm: sort edges by weight; take each edge that joins two different groups (Union-Find from episode 55). Joseph Kruskal, 1956.
  • Prim's algorithm: grow one tree from a start node; always add the cheapest edge from the tree to a node outside.
  • Dense / sparse graph: dense = close to n² edges (every pair, like today); sparse = few edges (like a road map).

Problem statement

LeetCode 1584, Min Cost to Connect All Points. Given points[i] = [x, y], the cost to connect two points is their Manhattan distance. Return the minimum cost to make all points connected (exactly one simple path between any two points).

points Answer
[[0,0],[2,2],[3,10],[5,2],[7,0]] 20
[[3,12],[-2,5],[-4,1]] 18

Constraints: 1 ≤ n ≤ 1000, -10^6 ≤ x, y ≤ 10^6, all points distinct.

All Java versions use this distance helper:

    static int dist(int[][] p, int i, int j) {
        return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);
    }

Obvious idea: try every set of n - 1 cables

List all n(n - 1)/2 pairs, try every set of n - 1 of them, and keep the cheapest set with no loop (checked with episode 55's Union-Find).

import java.util.*;

public class Main {
    static int dist(int[][] p, int i, int j) {
        return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);
    }
    static int[] parent, size;
    static void init(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }
    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
    static int best;
    static int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edges.add(new int[]{dist(points, i, j), i, j});
        best = Integer.MAX_VALUE;
        choose(edges, 0, new int[n - 1], 0, n);
        return n == 1 ? 0 : best;
    }
    static void choose(List<int[]> edges, int from, int[] pick, int got, int n) {
        if (got == n - 1) {
            init(n);
            int cost = 0;
            for (int e : pick) {
                if (!union(edges.get(e)[1], edges.get(e)[2])) return;
                cost += edges.get(e)[0];
            }
            best = Math.min(best, cost);
            return;
        }
        for (int e = from; e < edges.size(); e++) {
            pick[got] = e;
            choose(edges, e + 1, pick, got + 1, n);
        }
    }
    public static void main(String[] args) {
        System.out.println(minCostConnectPoints(new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}}));
        System.out.println(minCostConnectPoints(new int[][]{{3, 12}, {-2, 5}, {-4, 1}}));
    }
}
20
18

Correct. Now 12 offices at random spots:

import java.util.*;

public class Main {
    static int dist(int[][] p, int i, int j) {
        return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);
    }
    static int[] parent, size;
    static void init(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }
    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
    static int best;
    static int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edges.add(new int[]{dist(points, i, j), i, j});
        best = Integer.MAX_VALUE;
        choose(edges, 0, new int[n - 1], 0, n);
        return n == 1 ? 0 : best;
    }
    static void choose(List<int[]> edges, int from, int[] pick, int got, int n) {
        if (got == n - 1) {
            init(n);
            int cost = 0;
            for (int e : pick) {
                if (!union(edges.get(e)[1], edges.get(e)[2])) return;
                cost += edges.get(e)[0];
            }
            best = Math.min(best, cost);
            return;
        }
        for (int e = from; e < edges.size(); e++) {
            pick[got] = e;
            choose(edges, e + 1, pick, got + 1, n);
        }
    }
    public static void main(String[] args) {
        int n = 12;
        int[][] points = new int[n][];
        Random rnd = new Random(7);
        for (int i = 0; i < n; i++) points[i] = new int[]{rnd.nextInt(100), rnd.nextInt(100)};
        long t0 = System.nanoTime();
        int cost = minCostConnectPoints(points);
        System.out.println(cost + " metres, " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}
Time Limit Exceeded (stopped after 8 seconds)

Why it explodes: 12 points have 66 possible cables; choosing 11 of them is C(66, 11) ≈ 1 lakh crore sets.

The greedy trap: just the n - 1 cheapest cables

import java.util.*;

public class Main {
    static int dist(int[][] p, int i, int j) {
        return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);
    }
    static int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edges.add(new int[]{dist(points, i, j), i, j});
        edges.sort((a, b) -> Integer.compare(a[0], b[0]));
        int cost = 0;
        for (int k = 0; k < n - 1; k++) cost += edges.get(k)[0];
        return cost;
    }
    public static void main(String[] args) {
        System.out.println(minCostConnectPoints(new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}}));
        System.out.println(minCostConnectPoints(new int[][]{{3, 12}, {-2, 5}, {-4, 1}}));
    }
}
18
18

18 for example 1, cheaper than the true answer 20. The four cheapest cables are B-D 3, A-B 4, D-E 4, A-D 7 (with A = (0,0), B = (2,2), C = (3,10), D = (5,2), E = (7,0)). But A-B-D is a loop, and office C is not connected at all. Cheap is not enough: each cable must join two separate groups.

The key insight: the cheapest safe cable

Sort the cables cheapest first. Take them in order: if the two offices are already connected, skip (it would close a loop); if they are in different groups, lay it.

Why is that safe? (the cut property) Split the offices into two sides. Some cable in the best plan must cross the split. If the cheapest crossing cable e is not in it, add e: that makes a loop, which crosses the split somewhere else through a cable f that is at least as expensive. Remove f: still connected, and the total did not go up. So e can always be in an MST.

Kruskal on example 1 by hand:

Cable Cost Decision
B - D 3 lay
A - B 4 lay
D - E 4 lay
A - D 7 skip (A and D already connected through B)
A - E 7 skip
B - E 7 skip
B - C 9 lay: 4 cables for 5 offices, done

Total 3 + 4 + 4 + 9 = 20.

Solution 1 in Java: Kruskal (sort + Union-Find)

    static int[] parent, size;
    static void init(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }
    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
    static int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edges.add(new int[]{dist(points, i, j), i, j});
        edges.sort((a, b) -> Integer.compare(a[0], b[0]));
        init(n);
        int cost = 0, used = 0;
        for (int[] e : edges) {
            if (used == n - 1) break;
            if (union(e[1], e[2])) {
                cost += e[0];
                used++;
            }
        }
        return cost;
    }

Tests: the two examples, a single office, and two offices at the same spot:

20
18
0
2

The 12 offices that timed out, and LeetCode's biggest, 1,000 offices (about 5 lakh possible cables):

250 metres, 6 ms
1000 offices: 51991051 metres, 355 ms

Most of that time goes into creating and sorting the 5 lakh cables.

Solution 2 in Java: Prim (grow one tree), O(n²)

Start with office 0 in the tree. Keep best[v] = the cheapest cable from the tree to v. Each step: add the outside office with the smallest best, then let it offer cheaper cables to everyone outside. It is the same cut property, with the cut "inside the tree vs outside".

    static int minCostConnectPoints(int[][] points) {
        int n = points.length, cost = 0;
        int[] best = new int[n];
        Arrays.fill(best, Integer.MAX_VALUE);
        boolean[] inTree = new boolean[n];
        best[0] = 0;
        for (int step = 0; step < n; step++) {
            int u = -1;
            for (int v = 0; v < n; v++)
                if (!inTree[v] && (u == -1 || best[v] < best[u])) u = v;
            inTree[u] = true;
            cost += best[u];
            for (int v = 0; v < n; v++)
                if (!inTree[v]) best[v] = Math.min(best[v], dist(points, u, v));
        }
        return cost;
    }
20
18
0
2
1000 offices: 51991051 metres, 16 ms

The same total as Kruskal on 1,000 offices, and faster: there is no edge list and no sorting.

The same solution in C++ (Kruskal and Prim)

#include <bits/stdc++.h>
using namespace std;

// Min Cost to Connect All Points (LeetCode 1584): Kruskal (sort + Union-Find) and Prim (O(n^2) array version).
int dist(vector<vector<int>>& p, int i, int j) { return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]); }

vector<int> parent_, sz_;
int findRoot(int x) { return parent_[x] == x ? x : parent_[x] = findRoot(parent_[x]); }
bool unite(int a, int b) {
    int ra = findRoot(a), rb = findRoot(b);
    if (ra == rb) return false;
    if (sz_[ra] < sz_[rb]) swap(ra, rb);
    parent_[rb] = ra; sz_[ra] += sz_[rb];
    return true;
}

int kruskal(vector<vector<int>>& p) {
    int n = p.size();
    vector<array<int, 3>> edges;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) edges.push_back({dist(p, i, j), i, j});
    sort(edges.begin(), edges.end());
    parent_.assign(n, 0); iota(parent_.begin(), parent_.end(), 0); sz_.assign(n, 1);
    int cost = 0, used = 0;
    for (auto& [w, a, b] : edges) {
        if (used == n - 1) break;
        if (unite(a, b)) { cost += w; used++; }
    }
    return cost;
}

int prim(vector<vector<int>>& p) {
    int n = p.size(), cost = 0;
    vector<int> best(n, INT_MAX);
    vector<bool> inTree(n, false);
    best[0] = 0;
    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int v = 0; v < n; v++)
            if (!inTree[v] && (u == -1 || best[v] < best[u])) u = v;
        inTree[u] = true;
        cost += best[u];
        for (int v = 0; v < n; v++)
            if (!inTree[v]) best[v] = min(best[v], dist(p, u, v));
    }
    return cost;
}

int main() {
    vector<vector<int>> ex1 = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}}, ex2 = {{3, 12}, {-2, 5}, {-4, 1}};
    cout << kruskal(ex1) << " " << prim(ex1) << "\n";
    cout << kruskal(ex2) << " " << prim(ex2) << "\n";
}
20 20
18 18

The same solution in Python (Prim and Kruskal)

# Min Cost to Connect All Points (LeetCode 1584): Prim, O(n^2) array version (no edge list, no sorting),
# and Kruskal (sort + Union-Find) for comparison.
def dist(p, i, j):
    return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1])

def prim(points):
    n = len(points)
    best = [float("inf")] * n
    in_tree = [False] * n
    best[0] = 0
    cost = 0
    for _ in range(n):
        u = min((v for v in range(n) if not in_tree[v]), key=lambda v: best[v])
        in_tree[u] = True
        cost += best[u]
        for v in range(n):
            if not in_tree[v]:
                best[v] = min(best[v], dist(points, u, v))
    return cost

def kruskal(points):
    n = len(points)
    edges = sorted((dist(points, i, j), i, j) for i in range(n) for j in range(i + 1, n))
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving: a loop version of path compression
            x = parent[x]
        return x
    cost = used = 0
    for w, a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            cost += w
            used += 1
            if used == n - 1:
                break
    return cost

ex1 = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
ex2 = [[3, 12], [-2, 5], [-4, 1]]
print(prim(ex1), kruskal(ex1))
print(prim(ex2), kruskal(ex2))
20 20
18 18

Three real bugs

Bug 1: no cycle check (the n - 1 cheapest edges)

Shown above: 18 instead of 20, with a loop and office C left out. Fix: only lay a cable when union returns true.

Bug 2: Prim picks offices already in the tree

import java.util.*;

public class Main {
    static int dist(int[][] p, int i, int j) {
        return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);
    }
    static int minCostConnectPoints(int[][] points) {
        int n = points.length, cost = 0;
        int[] best = new int[n];
        Arrays.fill(best, Integer.MAX_VALUE);
        boolean[] inTree = new boolean[n];
        best[0] = 0;
        for (int step = 0; step < n; step++) {
            int u = -1;
            for (int v = 0; v < n; v++)
                if (u == -1 || best[v] < best[u]) u = v;
            inTree[u] = true;
            cost += best[u];
            for (int v = 0; v < n; v++)
                if (!inTree[v]) best[v] = Math.min(best[v], dist(points, u, v));
        }
        return cost;
    }
    public static void main(String[] args) {
        System.out.println(minCostConnectPoints(new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}}));
        System.out.println(minCostConnectPoints(new int[][]{{3, 12}, {-2, 5}, {-4, 1}}));
    }
}
0
0

0 and 0: office 0 has best = 0, so it is picked again and again and nobody else ever joins. Fix: if (!inTree[v] && ...).

Bug 3: a missing Math.abs

import java.util.*;

public class Main {
    static int dist(int[][] p, int i, int j) {
        return (p[i][0] - p[j][0]) + (p[i][1] - p[j][1]);
    }
    static int[] parent, size;
    static void init(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }
    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
    static int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edges.add(new int[]{dist(points, i, j), i, j});
        edges.sort((a, b) -> Integer.compare(a[0], b[0]));
        init(n);
        int cost = 0, used = 0;
        for (int[] e : edges) {
            if (used == n - 1) break;
            if (union(e[1], e[2])) {
                cost += e[0];
                used++;
            }
        }
        return cost;
    }
    public static void main(String[] args) {
        System.out.println(minCostConnectPoints(new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}}));
        System.out.println(minCostConnectPoints(new int[][]{{3, 12}, {-2, 5}, {-4, 1}}));
    }
}
-36
18

-36: x1 - x2 is negative when point i is to the left or below, so cables look like they pay us. Fix: Math.abs(...) + Math.abs(...).

Kruskal or Prim?

Kruskal Prim (array) Prim (heap)
Idea cheapest edges first, skip loops grow one tree grow one tree
Needs sorted edge list + Union-Find best[], inTree[] adjacency list + PriorityQueue
Time O(E log E) O(V²) O(E log V)
Space O(E) O(V) O(V + E)
Best for sparse graphs, edges given as a list dense graphs (every pair, like today) sparse graphs as adjacency lists

Complexity

Approach Time Space Test
Every set of n - 1 edges O(C(E, V-1) × V) O(E) 12 offices: Time Limit Exceeded
n - 1 cheapest edges O(E log E) O(E) wrong: 18 instead of 20
Kruskal O(E log E) O(E) 1,000 offices: under a second
Prim, array O(V²) O(V) 1,000 offices: faster

With every pair as an edge, E ≈ V²/2, so Kruskal is O(V² log V) and Prim's array version O(V²).

Common mistakes

Mistake What you see (real) Why Fix
n - 1 cheapest edges 18 instead of 20 loops; an office left out union() check (Kruskal)
Prim picks from all nodes 0 and 0 the same node again skip inTree[v]
No Math.abs -36 x1 - x2 can be negative |x1 - x2| + |y1 - y2|
Stopping Kruskal at n edges a loop, extra cost a tree has n - 1 edges stop at used == n - 1
Not checking connectivity (given edges) a "tree" that isn't one graph may be disconnected return -1 if used < n - 1
int total on huge inputs overflow sum > 2³¹ - 1 long

Mini project: the cabling plan

Kruskal on five Chandigarh sector offices (grid blocks), printing every cable it lays.

import java.util.*;

public class Main {
    // Mini project: the cabling plan. Kruskal, printing every cable it lays and every cable it skips.
    static int[] parent;
    static int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
    public static void main(String[] args) {
        String[] office = {"Sector 17", "Sector 22", "Sector 35", "Sector 8", "Sector 43"};
        int[][] p = {{17, 17}, {19, 16}, {21, 12}, {17, 22}, {20, 7}};   // grid blocks (x, y)
        int n = p.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edges.add(new int[]{Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]), i, j});
        edges.sort((a, b) -> Integer.compare(a[0], b[0]));
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int total = 0, used = 0;
        for (int[] e : edges) {
            if (used == n - 1) break;
            int a = find(e[1]), b = find(e[2]);
            String pair = office[e[1]] + " - " + office[e[2]];
            if (a == b) { System.out.printf("skip %-22s %2d blocks (already connected)%n", pair, e[0]); continue; }
            parent[a] = b; total += e[0]; used++;
            System.out.printf("lay  %-22s %2d blocks%n", pair, e[0]);
        }
        System.out.println("total: " + total + " blocks of cable");
    }
}
lay  Sector 17 - Sector 22   3 blocks
lay  Sector 17 - Sector 8    5 blocks
lay  Sector 22 - Sector 35   6 blocks
lay  Sector 35 - Sector 43   6 blocks
total: 20 blocks of cable

Practice

1. Connecting Cities With Minimum Cost (LeetCode 1135).

Solution

Edges are given, so Kruskal fits. If fewer than n - 1 cables get laid, the cities can't all be joined: -1.

import java.util.*;

public class Main {
    // Connecting Cities With Minimum Cost (LeetCode 1135): Kruskal on given edges; -1 if the cities can't all be joined.
    static int[] parent;
    static int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
    static int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, (a, b) -> Integer.compare(a[2], b[2]));
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        int cost = 0, used = 0;
        for (int[] c : connections) {
            int a = find(c[0]), b = find(c[1]);
            if (a == b) continue;
            parent[a] = b; cost += c[2];
            if (++used == n - 1) return cost;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(minimumCost(3, new int[][]{{1, 2, 5}, {1, 3, 6}, {2, 3, 1}}));
        System.out.println(minimumCost(4, new int[][]{{1, 2, 3}, {3, 4, 4}}));
    }
}
6
-1

2. Prim with a PriorityQueue.

Solution

Like Dijkstra (episode 52), but the key is the edge weight, not the distance from the start. Skip stale entries.

import java.util.*;

public class Main {
    // Prim with a PriorityQueue (lazy deletion, like Dijkstra in episode 52): O(E log V), good for sparse graphs.
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1, 4}, {0, 3, 7}, {1, 3, 3}, {1, 2, 9}, {3, 4, 4}, {2, 3, 10}, {1, 4, 7}};
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]}); adj.get(e[1]).add(new int[]{e[0], e[2]}); }
        boolean[] inTree = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.add(new int[]{0, 0});
        int cost = 0, added = 0;
        while (!pq.isEmpty() && added < n) {
            int[] top = pq.poll();
            if (inTree[top[0]]) continue;          // stale: this office joined already
            inTree[top[0]] = true; cost += top[1]; added++;
            for (int[] e : adj.get(top[0])) if (!inTree[e[0]]) pq.add(new int[]{e[0], e[1]});
        }
        System.out.println(added == n ? "MST cost " + cost : "not connected");
    }
}
MST cost 20

3. Print the cables of the MST.

Solution

In Prim, remember from[v]: the tree office that offered best[v].

import java.util.*;

public class Main {
    // Print the cables of the MST (Prim, array version): remember from[v], the tree office that offered best[v].
    public static void main(String[] args) {
        int[][] p = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
        int n = p.length;
        int[] best = new int[n], from = new int[n];
        Arrays.fill(best, Integer.MAX_VALUE);
        Arrays.fill(from, -1);
        boolean[] inTree = new boolean[n];
        best[0] = 0;
        int cost = 0;
        for (int step = 0; step < n; step++) {
            int u = -1;
            for (int v = 0; v < n; v++) if (!inTree[v] && (u == -1 || best[v] < best[u])) u = v;
            inTree[u] = true; cost += best[u];
            if (from[u] != -1) System.out.println("cable " + Arrays.toString(p[from[u]]) + " - " + Arrays.toString(p[u]) + ": " + best[u]);
            for (int v = 0; v < n; v++) {
                int d = Math.abs(p[u][0] - p[v][0]) + Math.abs(p[u][1] - p[v][1]);
                if (!inTree[v] && d < best[v]) { best[v] = d; from[v] = u; }
            }
        }
        System.out.println("total " + cost);
    }
}
cable [0, 0] - [2, 2]: 4
cable [2, 2] - [5, 2]: 3
cable [5, 2] - [7, 0]: 4
cable [2, 2] - [3, 10]: 9
total 20

4. Optimize Water Distribution in a Village (LeetCode 1168).

Solution

Building a well in house i = a pipe from a virtual house 0 with cost wells[i - 1]. Then it's an ordinary MST on n + 1 houses.

import java.util.*;

public class Main {
    // Optimize Water Distribution / Min Cost to Supply Water (LeetCode 1168): a well in house i = a pipe from a
    // virtual house 0 with cost wells[i-1]. Then it's an ordinary MST on n + 1 houses.
    static int[] parent;
    static int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
    static int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) edges.add(new int[]{0, i + 1, wells[i]});
        for (int[] pp : pipes) edges.add(pp);
        edges.sort((a, b) -> Integer.compare(a[2], b[2]));
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        int cost = 0;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a != b) { parent[a] = b; cost += e[2]; }
        }
        return cost;
    }
    public static void main(String[] args) {
        System.out.println(minCostToSupplyWater(3, new int[]{1, 2, 2}, new int[][]{{1, 2, 1}, {2, 3, 1}}));
        System.out.println(minCostToSupplyWater(2, new int[]{1, 1}, new int[][]{{1, 2, 1}, {1, 2, 2}}));
    }
}
3
2

Quick quiz

Edges: A-B 1, B-C 2, A-C 3, C-D 4, B-D 5. Total weight of the MST? A) 7 B) 6 C) 10 D) 8

Answer

A) 7. Kruskal: A-B 1 ✓, B-C 2 ✓, A-C 3 ✗ (loop), C-D 4 ✓. 1 + 2 + 4 = 7.

Interview questions

  1. How many edges does a spanning tree on n nodes have? Exactly n - 1.
  2. Why isn't "the n - 1 cheapest edges" correct? They can form a cycle and leave a node unconnected.
  3. State the cut property. For any split of the nodes, the cheapest edge crossing it belongs to some MST.
  4. Kruskal's complexity? O(E log E) for sorting, plus almost O(1) per Union-Find operation.
  5. Prim's complexity? O(V²) with arrays (best for dense graphs), O(E log V) with a binary heap.
  6. Does an MST give shortest paths? No. It minimises the total weight, not the distance between two particular nodes (that's Dijkstra).
  7. Do negative weights break MST algorithms? No. Kruskal and Prim only compare weights, so negative weights are fine.
  8. How would you get a maximum spanning tree? Sort in descending order (or negate the weights).

Glossary

Term Meaning
Tree Connected, no cycle; n - 1 edges
Spanning tree Edges connecting all nodes, no cycle
Minimum spanning tree (MST) The spanning tree with the least total weight
Manhattan distance |x1 - x2| + |y1 - y2|
Absolute value A number without its sign (Math.abs)
Greedy Take the best-looking choice now
Cut A split of the nodes into two sides
Cut property The cheapest crossing edge is in some MST
Kruskal Sort edges; add each one that joins two groups
Prim Grow one tree; add the cheapest edge leaving it
Dense / sparse Many edges (≈ n²) / few edges
Union-Find Episode 55's structure for "same group?"

Summary

  • A spanning tree connects all n nodes with n - 1 edges and no cycle; the MST has the least total weight.
  • Trying every set is exponential, and the n - 1 cheapest edges are a trap (loops, missing nodes).
  • Cut property: the cheapest edge joining two separate groups is safe.
  • Kruskal: sort + Union-Find, O(E log E). Prim: grow one tree, O(V²) for dense graphs like LeetCode 1584.
  • Watch for: no loop check, Prim re-picking tree nodes, and a missing Math.abs.
  • Next episode: word ladder (hard), BFS on a graph you build yourself.