Kruskal's algorithm

Kruskal's algorithm finds a minimum spanning tree of an undirected weighted graph: the cheapest set of edges that connects all its vertices. It works on a plain list of edges. Prim's algorithm builds the same tree by growing it from one vertex.

Explanation

A district has 4 villages joined by dirt roads, and paving each road costs a known amount. We want to pave some roads so that we can drive between any two villages on paved roads, and we want to spend as little as possible.

Fig. 1. The green roads are paved in order of cost. The red road isn't needed.

The natural plan is to pave the cheapest road first, then the next cheapest, and so on. Here the roads that cost 2, 2 and 3 connect every village for 7. Each paved road joined two villages that were not yet connected, so 4 villages need exactly 3 roads.

Six villages are harder.

Fig. 2. Pave roads so that every village can be reached, as cheaply as possible.

6 villages need 5 roads, and some of the cheap roads here form a cycle among themselves.

Following the small map, we pave the 5 cheapest roads. They cost 15 in total, and village 1 is left without a paved road.

Fig. 3. The red road joins two villages that were already connected. The blue road is the one village 1 needs.

The red road, which costs 5, joins villages 4 and 6, but they were already connected through village 5. The road village 1 needed, the blue one for 6, never got its turn.

So the question for each road is whether its two villages are already connected. If they are, skip the road. If not, pave it. We go through all the roads, cheapest first. On our map, the red road is now skipped, so the blue road gets its turn, and village 1 is connected.

Sometimes the connection is a long way round. The road that costs 7 joins villages 2 and 3, which are already connected through villages 4 and 5 by three paved roads. A search along the paved roads can visit every village for each road: with 100 000 villages and 100 000 roads, that is about 10 billion steps. So we keep groups instead. At first every village is its own group. Paving a road merges the groups of its two villages. Merging groups and asking whether two villages share one is what a disjoint set union does in nearly constant time per call.

This is Kruskal's algorithm: go through the roads from cheapest to dearest and pave each one that joins two different groups. The paved roads form a minimum spanning tree (MST): roads with no cycle that reach every village, at the smallest total cost.

Step through the whole run below. Before each step, say whether the road joins two groups.

Every village is its own group. The roads wait in order of cost, cheapest first.

The road 2–4 costs 1 and joins two different groups, so it is paved. The total is 1.

The road 5–6 costs 2 and joins two different groups, so it is paved. The total is 3.

The road 4–5 costs 3 and joins two different groups, so it is paved. The total is 6.

The road 3–5 costs 4 and joins two different groups, so it is paved. The total is 10.

The road 4–6 costs 5, but villages 4 and 6 are already in one group, so it is skipped.

The road 1–3 costs 6 and joins two different groups, so it is paved. The total is 16.

The road 2–3 costs 7, but villages 2 and 3 are already in one group, so it is skipped.

The road 2–5 costs 8, but villages 2 and 5 are already in one group, so it is skipped.

The road 1–2 costs 9, but villages 1 and 2 are already in one group, so it is skipped.

Every road has been checked. Five roads are paved, for a total of 16, and all six villages are in one group.

1/11

Fig. 4. Step through Kruskal's algorithm with the buttons. The boxes below hold the costs of the roads not checked yet, cheapest first. Villages of one colour form a group; a road between two groups is paved (green), a road inside a group is skipped (red).

The run connects all six villages with five roads for 16, the smallest possible total, and skips the other four roads.

The cheapest road between two groups is always safe to pave. When it comes up, every cheaper road has been paved or skipped, so each cheaper road lies inside one group. This road is then the cheapest way out of its village's group. Any plan has to leave that group by some road, and swapping that road for this one never costs more. The proof does this swap carefully.

Implementation

In graph terms, villages are vertices, roads are undirected edges, costs are weights, and a paved road is an edge taken. A group is a connected component of the edges taken so far. The DSU keeps the groups with its two calls: find(v) gives the root of the group of v, and unite(a, b) merges the groups of a and b and returns false if they were one group already.

1. Sort the edges by weight, smallest first.

2. Move to the next edge u–v of weight w.

3. Check the groups with unite(u, v). If it returns false, u and v were already in one group, and the edge is skipped.

4. Otherwise add w to total and count the edge in taken. Go back to step 2.

5. After the last edge, check the count. A spanning tree of n vertices has n - 1 edges, and each edge taken merges two groups. If taken < n - 1, more than one group is left, and the graph is not connected.

The program reads n and m, then m lines u v w: an undirected edge between u and v of weight w. It prints the total weight of a minimum spanning tree, or IMPOSSIBLE if the graph is not connected. Then it prints the edges of the tree, kept in tree, one pair per line. For the graph of Fig. 2 the input is:

6 9
1 2 9
1 3 6
2 3 7
2 4 1
2 5 8
3 5 4
4 5 3
4 6 5
5 6 2

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;

vector<int> parent, sz;

// find: the root of v's group
int find(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find(parent[v]);   // path compression
}

// unite: merge the groups of a and b; false if they were one group already
bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);        // union by size
    parent[b] = a;
    sz[a] += sz[b];
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<array<long long, 3>> edges(m);   // {w, u, v}: sort compares w first
    for (auto &e : edges) cin >> e[1] >> e[2] >> e[0];

    parent.resize(n + 1);
    sz.assign(n + 1, 1);
    for (int v = 1; v <= n; v++) parent[v] = v;   // every vertex is its own group

    // sort the edges
    sort(edges.begin(), edges.end());

    long long total = 0;
    int taken = 0;
    vector<pair<int, int>> tree;          // only needed to print the edges
    for (auto [w, u, v] : edges) {        // next edge
        if (!unite(u, v)) continue;       // check the groups: skip
        total += w;                       // count the edge as taken
        taken++;
        tree.push_back({u, v});           // only needed to print the edges
    }

    // check the count: fewer than n - 1 edges means the graph is not connected
    if (taken < n - 1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    cout << total << "\n";

    // print the edges of the tree; remove this block if you only need the total
    for (auto [u, v] : tree) cout << u << ' ' << v << '\n';
}

On the graph of Fig. 2 the program prints 16, then the edges of the tree in order of weight: 2 4, 5 6, 4 5, 3 5 and 1 3, one pair per line.

Sorting the m edges takes O(m \log m), and each call to unite is practically constant ($O(\alpha (n))$, the inverse Ackermann bound from the DSU article), so the sort sets the running time, O(m \log m). The memory is O(n + m).

If the graph is connected, the loop can also stop as soon as taken == n - 1: every edge after that is skipped anyway.

For a maximum spanning tree, sort the edges from the heaviest down, sort(edges.rbegin(), edges.rend()), and keep the rest of the loop.

Edges already built

Some problems say that a few edges are already built and ask for the cheapest way to finish the network. These edges cost nothing, so put them into the groups before the sorted loop:

for (auto [u, v] : built)
    if (unite(u, v)) taken++;   // free: the total doesn't change

Count them in taken only when unite returns true, so that the check taken < n - 1 stays correct. If edge 1–3 is already built on the graph of Fig. 2, the loop takes the edges 2–4, 5–6, 4–5 and 3–5, and the new edges weigh 10. The edge 1–3 is skipped when its turn comes.

Stopping at k groups

The number of groups is n - taken. Some problems ask for the smallest weight $d$ such that the edges of weight at most $d$ leave at most k groups. Run the loop and stop when k groups are left. The weight of the last edge taken, last, is the answer: without it there would be k + 1 groups.

long long last = 0;
for (auto [w, u, v] : edges) {
    if (n - taken == k) break;    // stop: k groups left
    if (!unite(u, v)) continue;
    last = w;
    taken++;
}
cout << last << '\n';

On the graph of Fig. 2 with k = 2, the loop stops after the edge 3–5, and the answer is 4. If k >= n, it stops at once and prints 0. If the graph has more than k connected components, no $d$ works and the loop never stops early: check n - taken <= k after it and print what the problem asks for that case.

Correctness proof

The algorithm keeps this invariant: the edges taken so far are part of some minimum spanning tree.

At the start no edge is taken, so the invariant holds. Suppose it holds, and the algorithm takes the edge $e$ between $u$ and $v$ of weight $w$. Let $S$ be the group of $u$ just before. Every edge that came up before $e$ joins two vertices of one group: it was either taken, and merged its groups, or skipped, because its ends were in one group already. Groups only grow, so none of these edges leaves $S$. All edges that come up after $e$ weigh at least $w$. So $e$ is a cheapest edge leaving $S$. On the graph of Fig. 2, when edge 4–5 of weight 3 comes up, the group of vertex 4 holds vertices 2 and 4, and the other edges out of it weigh 5, 7, 8 and 9.

Fig. 5. The tree's path from vertex 4 to vertex 5 leaves the group S by the red edge f. The blue edge e is the cheapest edge out of S.

In Fig. 5, $T$ is a spanning tree of weight 20 that doesn't contain $e$. Its path from vertex 4 to vertex 5 leaves $S$ by edge 2–3 of weight 7. Call that edge $f$. Remove $f$ and add $e$: every vertex is still connected, and the weight drops to 20 − 7 + 3 = 16, the tree the algorithm finds.

In general, let $T$ be a minimum spanning tree that contains the edges taken so far. If $T$ contains $e$, the invariant holds. Otherwise $T$ connects $u$ and $v$ by a path. It starts in $S$ and ends outside it, so it leaves $S$ by some edge $f$, and the weight of $f$ is at least $w$. $f$ is not an edge taken so far, because those all lie inside groups. Removing $f$ splits $T$ into two parts. The path from $u$ to $v$ in $T$ used $f$, so $u$ and $v$ are in different parts, and $e$ joins them again. The new spanning tree is no heavier than $T$, so it is also a minimum spanning tree, and it contains every edge taken, $e$ included.

On the map the swap made $T$ cheaper, so that $T$ wasn't minimum. When $f$ weighs the same as $e$, the swap keeps the weight, and that is how a minimum tree without $e$ becomes one that contains it.

When the loop ends in a connected graph, n - 1 edges are taken. They are part of a minimum spanning tree, which has n - 1 edges itself, so they are that tree.

Edges of equal weight may come in any order. Each order gives a minimum spanning tree, though not always the same one. The proof never adds weights along a path, it only compares two single edges, so negative weights are fine too.

Common mistakes

• Marking vertices instead of groups, so an edge is skipped when both its ends already have an edge taken, though they may still be in different groups. Compare the groups with unite, not marks on vertices.

• Storing edges as {u, v, w} and sorting them, so sort orders them by u instead of by weight. Store {w, u, v}, or sort with a comparator on the weight.

• Assuming the graph is connected, which prints a total even when some vertex is left alone. Count the edges taken, compare with n - 1 and print IMPOSSIBLE when there are fewer.

Similar algorithms

Prim's algorithm grows the same minimum spanning tree from one vertex with a priority queue. Kruskal is shorter to write from a list of edges and gives the groups along the way, which the variants above use. With a few hundred points as vertices, all n(n - 1)/2 \approx 10^5 pairs fit as edges and Kruskal works. With 5000 points there are about 1.25 \cdot 10^7 pairs, about 300 MB as array<long long, 3>, and Prim's O(n^2) version needs no edge list.

Dijkstra's algorithm finds the shortest routes from one vertex, a different question. A minimum spanning tree can make a route long: on the graph of Fig. 2, the tree's path from vertex 1 to vertex 2 weighs 6 + 4 + 3 + 1 = 14, while the direct edge weighs 9.

If all edges have the same weight, every spanning tree is a minimum one, and BFS or DFS finds one in O(n + m).

Practice