Minimum Spanning Trees

What Is a Minimum Spanning Tree?

12 min board

What to say

Given a connected, undirected, weighted graph G = (V, E), a spanning tree includes all vertices, has no cycles and has exactly |V| − 1 edges.
A minimum spanning tree is the spanning tree with the smallest total edge weight.
Where it is used: network design (roads, cables), clustering, image segmentation, approximations for hard optimisation problems.
Put the example graph on the board — it is used by both algorithms for the rest of the lecture.

Spanning tree and MST

A spanning tree of G = (V, E) is a subgraph that:

includes all vertices in V
is a tree (no cycles)
has exactly |V| − 1 edges

A minimum spanning tree (MST) is the spanning tree with the smallest possible total edge weight. MSTs are used in network design (roads, cables), clustering, image segmentation, and approximations for hard optimisation problems.

Example graph · n = 6, m = 9

Input format: n m, then lines x y w (vertices from 1).

MST edges (weight): (1,2,1), (2,5,1), (2,6,2), (3,4,4), (1,3,5) — total cost 13.

Key Properties of MSTs

8 min board

What to say

Exactly |V| − 1 edges and no cycles — so an algorithm can stop after |V| − 1 accepted edges.
The cut property is what both algorithms rely on: the lightest edge crossing any cut belongs to some MST.
The cycle property is the mirror image: the heaviest edge of a cycle is never needed.

Four properties

An MST has exactly |V| − 1 edges and no cycles.
Adding any edge to the MST creates a cycle; removing any MST edge disconnects the graph.
Cut property: for any cut (partition of the vertices), the lightest edge crossing the cut belongs to at least one MST.
Cycle property: in any cycle, the heaviest edge cannot be in an MST.

Kruskal's Algorithm

35 min code demo: union-find demo: Kruskal

What to say

Idea: sort the edges by weight and add them one by one, skipping every edge that would create a cycle.
To detect a cycle quickly we need one question answered fast: are u and v already connected? That is the Disjoint Set Union — find and unite.
Show the DSU demo: union a few pairs with the naive version, watch the chain grow, then switch to the optimised one — path compression and union by rank.
Then the code: the DSU, the edge with operator<, and main — sort, unite, stop at n − 1 edges.
Walk through the example on the board, then let the Kruskal demo do a random graph.
Total O(E log E) — the sort dominates; each DSU operation is almost O(1).

Idea and steps

Sort edges by weight and add them one by one, skipping edges that would create a cycle. A Disjoint Set Union (DSU), also called Union-Find, quickly detects cycles.

Sort all edges in non-decreasing order of weight.
Initialise the DSU so each vertex is its own set.
For each edge (u, v, w) in order: if find(u) != find(v), add the edge to the MST and union the sets.
Stop when |V| − 1 edges are chosen.

Complexity

Part	Cost
Sorting edges	O(E log E)
DSU operations	almost O(1) each (inverse Ackermann)
Total	O(E log E)

Demo · union-find, with and without compression

components

deepest chain

steps in last find

—

Ten singleton sets. Union a few pairs, then switch to naive and compare the depth.

1 · The DSU

struct DSU {
    vector<int> parent, rank;
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int v) {
        if (parent[v] == v) return v;
        return parent[v] = find(parent[v]); // path compression
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;          // already in same set
        if (rank[a] < rank[b]) swap(a, b); // union by rank
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
        return true;
    }
};

find returns the root of the set and, on the way back, points every node straight at it (path compression). unite hangs the lower tree under the higher one (union by rank) and returns false when both ends are already in one set — that edge would close a cycle.

2 · The edge

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const { return w < other.w; }
};

operator< compares by weight, so sort puts the lightest edges first.

3 · main

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    edges.reserve(m);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        edges.push_back({x - 1, y - 1, w});
    }

    sort(edges.begin(), edges.end());
    DSU dsu(n);

    int mst_cost = 0;
    vector<Edge> mst;

    for (auto &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst.push_back(e);
            mst_cost += e.w;
        }
        if ((int)mst.size() == n - 1) break;
    }

    cout << "MST cost: " << mst_cost << "\nEdges:\n";
    for (auto &e : mst) {
        cout << e.u + 1 << " - " << e.v + 1 << " (" << e.w << ")\n";
    }
    return 0;
}

input

output

MST cost: 13
Edges:
1 - 2 (1)
2 - 5 (1)
2 - 6 (2)
3 - 4 (4)
1 - 3 (5)

Walkthrough on the example

Edges sorted: (1,2,1), (2,5,1), (2,6,2), (1,5,3), (3,4,4), (1,3,5), (5,6,6), (1,4,8), (2,4,9)

Start: sets {1}, {2}, {3}, {4}, {5}, {6}
Add  (1,2,1): merge {1} with {2}
Add  (2,5,1): merge {1,2} with {5}
Add  (2,6,2): merge {1,2,5} with {6}
Skip (1,5,3): 1 and 5 are already in one set — would create a cycle
Add  (3,4,4): merge {3} with {4}
Add  (1,3,5): merge {1,2,5,6} with {3,4}
MST edges: (1,2), (2,5), (2,6), (3,4), (1,3) with total cost 13

Five edges are taken, so the loop stops there: n − 1 = 5. Of the remaining edges only (1,5,3) was looked at, and it would have closed the cycle 1 – 2 – 5.

Demo · Kruskal, edge by edge

MST cost

edges taken

0 / 0

rejected (cycles)

w	edge	find(u)	find(v)	verdict

Edges are sorted by weight. Step through and watch which ones DSU rejects.

Another version · edges as pairs

The edge is stored as pair<w, pair<x, y>>, so plain sort orders by weight with no comparator. The DSU is two arrays and two functions:

int find(int v) {
    if (p[v] == v)
        return v;
    p[v] = find(p[v]);
    return p[v];
}

void union_set(int v, int u) {
    v = find(v);
    u = find(u);
    if (r[v] < r[u])
        p[v] = u;
    else if (r[u] < r[v])
        p[u] = v;
    else {
        p[u] = v;
        r[v]++;
    }
}

the full program — version 261 lines

#include <iostream>
#include <vector>
#include <algorithm>   // added: sort lives here
#define pb push_back
#define mp make_pair
#define f first
#define s second 

using namespace std;
vector<pair<int, pair<int, int> > > g;
int p[100];
int r[100];
int n, m, x, y, w;

int find(int v) {
    if (p[v] == v)
        return v;
    p[v] = find(p[v]);
    return p[v];
}

void union_set(int v, int u) {
    v = find(v);
    u = find(u);
    if (r[v] < r[u])
        p[v] = u;
    else if (r[u] < r[v])
        p[u] = v;
    else {
        p[u] = v;
        r[v]++;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> w;
        x--;
        y--;
        g.pb(mp(w, mp(x, y)));
    }
    sort(g.begin(), g.end());
    for (int i = 0; i < n; i++)
        p[i] = i;
    // for (int i = 0; i < m; i++) 
    //     cout << g[i].s.f << " " << g[i].s.s << " " << g[i].f << endl;
    int sum = 0;
    for (int i = 0; i < m; i++) {
        int v = g[i].s.f;
        int u = g[i].s.s;

        if (find(v) != find(u)) {
            union_set(u, v);
            sum += g[i].f;
            cout << g[i].s.f + 1 << " " << g[i].s.s + 1 << endl;
        }
    }
    cout << sum;
    return 0;
}

output

It prints each chosen edge and then the total.

Prim's Algorithm

30 min code

What to say

Idea: grow the MST from a start vertex, each time taking the lightest edge that connects the tree to a new vertex.
The dense version: key[v] is the lightest edge from the tree to v. Pick the unused vertex with the smallest key, mark it, update the keys of its neighbours.
This is O(V²); with a min-heap it becomes O(E log V).
Walk through the example from vertex 1 and show that the cost is the same 13 as Kruskal.
Then the two other versions: one that remembers the parent and prints the edges, and one that uses −1 for "not reached yet" — and the trap that comes with it.

Idea and steps

Grow the MST from an arbitrary start vertex by repeatedly picking the minimum-weight edge that connects the current tree to a new vertex. Below is the dense O(V²) version — scan all vertices to find the next minimum key. A min-heap version improves it to O(E log V).

Set key[start] = 0, all others to infinity.
Repeat n times: pick the unused vertex v with the smallest key[v]; mark v used; for each neighbour (to, w), if w < key[to], update key[to] and record the parent.
The keys of the chosen edges and the parents describe the MST.

Complexity

Version	Cost
Dense scan (below)	O(V²)
With a binary heap	O(E log V)

The program

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        --x; --y;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    const int INF = 1e9;
    vector<int> key(n, INF), parent(n, -1), used(n, 0);

    key[0] = 0; // start from vertex 0
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!used[j] && (v == -1 || key[j] < key[v])) v = j;
        }
        used[v] = 1;
        for (auto [to, w] : g[v]) {
            if (!used[to] && w < key[to]) {
                key[to] = w;
                parent[to] = v;
            }
        }
    }

    int total = 0;
    for (int w : key) total += w;

    cout << "MST cost: " << total << "\nEdges:\n";
    for (int v = 1; v < n; v++) {
        cout << parent[v] + 1 << " - " << v + 1 << " (" << key[v] << ")\n";
    }
    return 0;
}

input

output

MST cost: 13
Edges:
1 - 2 (1)
1 - 3 (5)
3 - 4 (4)
2 - 5 (1)
2 - 6 (2)

The total is the sum of the keys: the key of each vertex is the weight of the edge that attached it to the tree.

Walkthrough on the example

Start at 1: key[2] ∞ → 1, key[3] ∞ → 5, key[4] ∞ → 8, key[5] ∞ → 3
Pick 2 via (1,2,1): key[5] 3 → 1, key[6] ∞ → 2
Pick 5 via (2,5,1): no key improves
Pick 6 via (2,6,2): no key improves
Pick 3 via (1,3,5): key[4] 8 → 4
Pick 4 via (3,4,4): no key improves
MST cost 13: (1,2), (1,3), (3,4), (2,5), (2,6)

The order of attaching is 1, 2, 5, 6, 3, 4 — the same five edges as Kruskal, found in a different order, cost 13.

Another version · with a parent array

The same O(V²) loop on global arrays: d for the keys, u for used, p for the parent. At the end it prints each vertex with its parent — the edges of the MST.

the full program — version 261 lines

#include <iostream>
#include <vector>
#define mp make_pair
#define pb push_back

using namespace std;

vector<pair<int, int > > g[100];
int n, m, x, y, w;
int d[100];
int u[100];
int p[100];

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> w;
        x--;
        y--;
        g[x].pb(mp(y, w));
        g[y].pb(mp(x, w));
    }
    int INF = 1000000;
    for (int i = 0; i < n; i++)
        d[i] = INF;
    d[0] = 0;

    for (int i = 0; i < n; i++) {
        // step 1
        int v = -1;
        for (int j = 0; j < n; j++)
            if (u[j] == 0) 
                if (v == -1 || d[v] > d[j])
                    v = j;
        u[v] = true;
        // step 2
        for (int j = 0; j < g[v].size(); j++) {
            int k = g[v][j].first;
            int l = g[v][j].second;
            if (u[k] == false && d[k] > l) {
                d[k] = l;
                p[k] = v;
            }
        }

        // for (int j = 0; j < n; j++)
        //     cout << u[j] << " ";
        // cout << endl;
        // for (int j = 0; j < n; j++) 
        //     cout << d[j] << " ";
        // cout << endl;
        // for (int j = 0; j < n; j++) 
        //     cout << p[j] << " ";
        // cout << endl;
        // cout << endl;
    }
    for (int j = 0; j < n; j++)
        if (p[j] != j)
            cout << j + 1 << " " << p[j] + 1 << endl;
    return 0;
}

output

Another version · −1 instead of infinity

Here "not reached yet" is −1 instead of a large number. Then choosing the next vertex needs an extra condition: an unreached vertex must never be picked while a reached one is available.

        int v = -1;
        for (int j = 0; j < n; j++) {
            // fixed: skip unreached vertices (d == -1), otherwise one could be picked
            if (u[j] == 0 && d[j] != -1 && (v == -1 || d[v] > d[j]))
                v = j;
        }

Without d[j] != -1 the first unused vertex is taken as the starting candidate even when it is unreached, and d[v] > d[j] with d[v] = -1 is never true, so it is never replaced.

the full program — version 345 lines

#include <iostream>
#include <vector>
#define mp make_pair
#define pb push_back

using namespace std;
int n, m, x, y, w;
vector<pair<int, int> > g[100];
int d[100];
int u[100];


int main() {
    cin >> n >> m; 
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> w;
        x--;
        y--;
        g[x].pb(mp(y, w));
        g[y].pb(mp(x, w));
    }
    for (int i = 0; i < n; i++)
        d[i] = -1;
    d[0] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            // fixed: skip unreached vertices (d == -1), otherwise one could be picked
            if (u[j] == 0 && d[j] != -1 && (v == -1 || d[v] > d[j]))
                v = j;
        }
        u[v] = 1;
        for (int j = 0; j < g[v].size(); j++) {
            int x = g[v][j].first;
            int w = g[v][j].second;
            if (u[x] == 0 && (d[x] == -1 || d[x] > w))
                d[x] = w;
        }
    }

    for (int i = 0; i < n; i++)
        cout << d[i] << " ";

    return 0;
}

output

0 1 5 4 1 2

It prints the key of every vertex; their sum, 13, is the MST cost.

Kruskal vs Prim

5 min board

Which one when

Algorithm	Best For	Data Structures	Complexity
Kruskal	sparse graphs, edge list input	sort edges + DSU	O(E log E)
Prim	dense graphs or adjacency list	min-heap + visited set	O(E log V) (or O(V²))

Takeaways

3 min

Four things to remember

MSTs connect all vertices with minimum total weight and no cycles.
Kruskal: sort the edges, add the lightest non-cycle edges using DSU.
Prim: grow from a start vertex, always choose the lightest outgoing edge.
Both algorithms give the same MST cost on connected undirected weighted graphs.

Lab 11 — the problems

12 min ADS-Lab-11

What to say

Four of the five problems are Kruskal with a different story around it.
The total can exceed int: with m up to 2·10⁵ and weights up to 10⁹ it reaches 2·10¹⁴ — use long long.
Labs 11 and 12 are defended together, in the final teaching week, with one problem from each lab.

Problem to topic

Hana Kageroukey

Kruskal at scale, n, m ≤ 2·10⁵ — long long and the optimised DSU

Duck Islandskey

Kruskal where the weight is computed from the island data

Travellingkey

Kruskal with two road types — read the weight rule carefully

Minimal costkey

Matrix input, n ≤ 50, existing edges cost nothing — start here

Nugman and Graph 2

Vertices deleted one by one; process the queries in reverse so deletion becomes union