Minimum Spanning Trees · Algorithms (DAA)

A spanning tree of a connected, undirected graph is a subset of its edges that connects all vertices with no cycles — exactly V − 1 edges. A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight.

Uses: laying cable or pipelines to connect cities at minimum cost, designing networks, clustering, and approximating harder problems like TSP.

A weighted graph with its minimum spanning tree highlighted: C–E (2), A–B (4), C–F (5), C–D (7) and A–F (8), total weight 26. Because all weights are distinct, this MST is unique.

Kruskal's algorithm

Greedy rule: consider edges from lightest to heaviest; add an edge if it does not create a cycle.

To test "would this edge create a cycle?" quickly, Kruskal uses a union-find (disjoint set) structure: each vertex starts in its own set; an edge (u, v) creates a cycle exactly when u and v are already in the same set.

C++

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

struct Edge { int u, v, w; };
vector<int> parent;
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }   // path compression

int main() {
    const char *name = "ABCDEF";
    vector<Edge> edges = {{0,1,4},{0,5,8},{1,2,10},{1,5,11},{2,3,7},{2,4,2},{2,5,5},{3,4,9},{4,5,6},{3,5,14}};
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; });
    parent.resize(6);
    iota(parent.begin(), parent.end(), 0);
    int total = 0, used = 0;
    for (const Edge &e : edges) {
        int ru = find(e.u), rv = find(e.v);
        cout << name[e.u] << "-" << name[e.v] << " (" << e.w << "): ";
        if (ru == rv) { cout << "skip, would form a cycle" << endl; continue; }
        parent[ru] = rv;                                   // union the two trees
        total += e.w;
        cout << "take" << endl;
        if (++used == 5) break;                            // V - 1 edges: done
    }
    cout << "MST weight = " << total << endl;
    return 0;
}

Output

C-E (2): take
A-B (4): take
C-F (5): take
E-F (6): skip, would form a cycle
C-D (7): take
A-F (8): take
MST weight = 26

Try it Yourself

Time: sorting dominates → O(E log E) (= O(E log V)).

Prim's algorithm

Greedy rule: grow one tree from a start vertex; at each step add the cheapest edge connecting the tree to a new vertex. A min-priority queue holds the candidate edges.

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    const char *name = "ABCDEF";
    int V = 6;
    vector<vector<pair<int, int>>> adj(V);          // (neighbour, weight)
    int e[][3] = {{0,1,4},{0,5,8},{1,2,10},{1,5,11},{2,3,7},{2,4,2},{2,5,5},{3,4,9},{4,5,6},{3,5,14}};
    for (auto &x : e) { adj[x[0]].push_back({x[1], x[2]}); adj[x[1]].push_back({x[0], x[2]}); }

    vector<bool> inTree(V, false);
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;   // (weight, vertex, from)
    pq.push({0, 0, -1});
    int total = 0;
    while (!pq.empty()) {
        auto [w, v, from] = pq.top(); pq.pop();
        if (inTree[v]) continue;                     // stale entry
        inTree[v] = true;
        total += w;
        if (from >= 0) cout << "add " << name[from] << "-" << name[v] << " (" << w << ")" << endl;
        for (auto [to, wt] : adj[v])
            if (!inTree[to]) pq.push({wt, to, v});
    }
    cout << "MST weight = " << total << endl;
    return 0;
}

Output

add A-B (4)
add A-F (8)
add F-C (5)
add C-E (2)
add C-D (7)
MST weight = 26

Try it Yourself

Time with a binary heap: O(E log V). With an adjacency matrix and no heap: O(V²), which is better for dense graphs.

Kruskal vs Prim

	Kruskal	Prim
Grows	a forest that merges into one tree	a single tree
Picks	globally lightest safe edge	lightest edge leaving the tree
Data structure	sorted edges + union-find	priority queue
Time	O(E log E)	O(E log V) with a heap; O(V²) with a matrix
Better for	sparse graphs	dense graphs

Both always find a minimum spanning tree. If all edge weights are distinct, the MST is unique, so both find the same one.

Test yourself

4 questions · pick an answer to check it instantly

1
How many edges does a spanning tree of a graph with 10 vertices have?
2
What does Kruskal's algorithm use to detect cycles efficiently?
3
Which algorithm grows a single tree from a start vertex?
4
What is Kruskal's running time?

#Kruskal's algorithm

#Prim's algorithm

#Kruskal vs Prim

Test yourself

Kruskal's algorithm

Prim's algorithm

Kruskal vs Prim