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
nnodes has exactlyn - 1edges: fewer can't connect everyone, more must make a cycle. - Spanning tree: a set of edges that connects all
nnodes 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|:xwithout its sign; JavaMath.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
- How many edges does a spanning tree on n nodes have? Exactly
n - 1. - Why isn't "the n - 1 cheapest edges" correct? They can form a cycle and leave a node unconnected.
- State the cut property. For any split of the nodes, the cheapest edge crossing it belongs to some MST.
- Kruskal's complexity? O(E log E) for sorting, plus almost O(1) per Union-Find operation.
- Prim's complexity? O(V²) with arrays (best for dense graphs), O(E log V) with a binary heap.
- Does an MST give shortest paths? No. It minimises the total weight, not the distance between two particular nodes (that's Dijkstra).
- Do negative weights break MST algorithms? No. Kruskal and Prim only compare weights, so negative weights are fine.
- 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
nnodes withn - 1edges 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.