Implement Kruskals Algorithm

The problem, simply

You get V towns and a list of possible two-way roads, each with a building price. Choose some roads so that every town can reach every other town, and the total price is as small as possible.

The chosen roads never form a loop, because a loop always has one road you could drop and stay connected. So the answer uses exactly V - 1 roads. Give back the total price (and, if asked, the roads).

A story to remember it

Picture it

Examples

Way 1: the simple way

Same greedy idea, slow loop check. Sort the roads by price. For each road, ask "can I already get from one end to the other using the roads I built?" by running a breadth first search over the built roads.

1. Sort the roads from cheapest to most expensive.
2. For each road a-b: search from a over the built roads. If b is found, skip the road.
3. Otherwise build it. Stop when you have V - 1 roads.

import java.util.*;

class Solution {
    public int spanningTree(int V, int[][] edges) {
        int[][] roads = edges.clone();
        Arrays.sort(roads, (x, y) -> x[2] - y[2]);           // cheapest first
        List<List<Integer>> built = new ArrayList<>();
        for (int i = 0; i < V; i++) built.add(new ArrayList<>());
        int cost = 0, count = 0;
        for (int[] r : roads) {
            if (count == V - 1) break;
            if (connected(built, r[0], r[1], V)) continue;    // would make a loop
            built.get(r[0]).add(r[1]);
            built.get(r[1]).add(r[0]);
            cost += r[2];
            count++;
        }
        return cost;
    }

    private boolean connected(List<List<Integer>> built, int a, int b, int V) {
        boolean[] seen = new boolean[V];
        Queue<Integer> line = new ArrayDeque<>();
        line.add(a);
        seen[a] = true;
        while (!line.isEmpty()) {
            int u = line.poll();
            if (u == b) return true;
            for (int v : built.get(u)) {
                if (!seen[v]) { seen[v] = true; line.add(v); }
            }
        }
        return false;
    }
}

How long it takes: sorting is O(E log E), but then each of the E roads may run a search over the built roads. There are fewer than V built roads, so one search is O(V), and all of them together are O(E * V). Extra room: the built roads and the search, O(V + E).

Way 2: the clever way

Replace the search with team captains. Every town remembers a parent. Follow parents up until you reach a town that is its own parent: that is the captain. Two towns are connected exactly when they have the same captain.

1. Sort the roads by price.
2. Every town starts as its own captain: parent[i] = i.
3. For each road a-b, find both captains. Same captain: skip. Different: build the road and make one captain point to the other.
4. Stop after V - 1 roads.

Two small tricks keep the parent chains short. When you find a captain, point every town you passed straight at it (path compression). When two teams join, hang the shorter tree under the taller one (union by rank).

import java.util.*;

class Solution {
    private int[] parent, rank;

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // point straight at the captain
        return parent[x];
    }

    private boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                          // same team: a loop
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    }

    public int spanningTree(int V, int[][] edges) {
        int[][] roads = edges.clone();
        Arrays.sort(roads, (x, y) -> Integer.compare(x[2], y[2]));
        parent = new int[V];
        rank = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;          // everyone is their own captain
        int cost = 0, count = 0;
        for (int[] r : roads) {
            if (count == V - 1) break;                       // already connected
            if (union(r[0], r[1])) {
                cost += r[2];
                count++;
            }
        }
        return cost;
    }
}

How long it takes: sorting the roads is O(E log E). Each find and union is almost constant time with both tricks, so the loop is about O(E). Total O(E log E), which is the same as O(E log V). Extra room: the parent and rank arrays plus the sorted copy, O(V + E).

Watch out for

• Sorting with x[2] - y[2] can overflow if prices are huge or very negative. Integer.compare is safe.
• A graph that is not connected never reaches V - 1 roads. You get a cheapest forest instead. Check count == V - 1 if the problem says to report that.
• Negative prices are fine. Kruskal only compares prices, it never adds them along a path.
• Sorting the caller's array changes their input. Sort a copy if that matters.

What interviewers ask next

• Why is cheapest-first safe? Take any split of the towns into two groups. The cheapest road crossing the split is always in some cheapest network, and Kruskal only ever builds such roads (the cut property).
• Kruskal or Prim? Kruskal shines when the roads come as a list and the map is sparse. Prim with a heap works from a neighbour list and is better on dense maps.
• Is the cheapest network unique? Yes when all prices are different. With equal prices there can be several, all with the same total.
• Maximum spanning tree? Sort from most expensive to cheapest and run the same code.
• Connect cities where some roads already exist for free? Union those first, then run Kruskal on the rest.

Remember this

Grown-up words: towns are vertices, roads are weighted edges, the cheapest connected network is a minimum spanning tree (MST), teams with captains are a disjoint set union (union find), the captain is the root or representative, pointing straight at the captain is path compression, hanging the short tree under the tall one is union by rank, and the method is Kruskal's algorithm.