Minimum Spanning Tree: Kruskal's Algorithm

Lesson 14 of 17 · Graphs and trees

Kruskal's algorithm sorts all the edges from the cheapest one and adds them in order – except those that would make a cycle. Whether an edge makes a cycle is checked quickly by the DSU (Union-Find) structure.

Before you start: prerequisites – DSU, Prim's algorithm.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The idea

All the towns have to be connected by roads so that every town can be reached from every other one, and the total price of the roads is the lowest. The chosen edges then form a tree (a cycle would mean one unnecessary road) that covers all the vertices – a minimum spanning tree (MST). It has exactly n − 1 edges.

        4
   1 ------- 2
   |  \      |
 1 |   \ 7   | 2
   |    \    |
   3 ------- 4 ---- 5
        5       3

The edges: 1–2 (4), 1–3 (1), 1–4 (7), 2–4 (2), 3–4 (5), 4–5 (3).

Kruskal: in total 1 + 2 + 3 + 4 = 10
Edge (in order of weight)Are the ends already connected?Decision
1–3 (1)nowe take it
2–4 (2)nowe take it
4–5 (3)nowe take it
1–2 (4)nowe take it – now all are connected (4 edges)
3–4 (5)yeswe skip it (a cycle)
1–4 (7)yeswe skip it

Why DSU?

DSU keeps a division of the vertices into groups (components). The operation findSet(v) returns the representative of the group of the vertex v, and unite(a, b) joins two groups. The edge u–v makes a cycle exactly when u and v are already in the same group. With path compression and union by size both operations are practically O(1).

The program

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

struct Edge { int w, u, v; };        // the weight first, so that sorting goes by weight

vector<int> parent, sz;

int findSet(int v) {                 // the representative of the group, with path compression
    if (parent[v] == v) return v;
    return parent[v] = findSet(parent[v]);
}

bool unite(int a, int b) {           // returns false if they are already in the same group
    a = findSet(a);
    b = findSet(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);   // we attach the smaller group to the larger one
    parent[b] = a;
    sz[a] += sz[b];
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> g(m);
    for (auto &e : g) cin >> e.u >> e.v >> e.w;
    sort(g.begin(), g.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; });
    parent.resize(n + 1);
    iota(parent.begin(), parent.end(), 0);   // parent[v] = v
    sz.assign(n + 1, 1);
    long long total = 0;
    vector<Edge> chosen;
    for (auto &e : g)
        if (unite(e.u, e.v)) {         // the ends were in different groups
            total += e.w;
            chosen.push_back(e);
        }
    if ((int)chosen.size() != n - 1) {
        cout << "the graph is not connected" << endl;
        return 0;
    }
    cout << total << endl;
    for (auto &e : chosen) cout << e.u << " " << e.v << " " << e.w << endl;
    return 0;
}

Example (the graph from the drawing)

Input

5 6
1 2 4
1 3 1
1 4 7
2 4 2
3 4 5
4 5 3

Output

10
1 3 1
2 4 2
4 5 3
1 2 4

The complexity is determined by sorting: O(m log m).

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: harder

Splitting into k groups

n students and m pairs with a "distance" u v d are given. The students have to be split into exactly k groups so that the smallest distance between two students from different groups is as large as possible. Print that distance. (The graph is connected, 2 ≤ k ≤ n.)

Example 1

Input

5 6 3
1 2 1
2 3 2
3 4 5
4 5 1
1 5 6
2 4 4

Output

2

Example 2

Input

5 6 2
1 2 1
2 3 2
3 4 5
4 5 1
1 5 6
2 4 4

Output

4
Common mistakes and tips
  • Sort the edges by weight, not by vertices.
  • If fewer than n − 1 edges are chosen, the graph is not connected.
  • Without path compression findSet can be O(n) and the program becomes slow.

Check your knowledge

Open the quiz

Kruskal's algorithm

1. In which order does Kruskal consider the edges?




2. When does Kruskal skip the edge u–v?




3. What determines the complexity of Kruskal's algorithm?