Prim's algorithm versus Kruskal's

Why it matters

A company wants to lay fibre cables between offices. Each possible cable has a cost. The company needs every office connected to every other office, directly or through other offices, and it wants the total cost as low as possible. It does not need a cable between every pair. Any extra cable only adds cost.

This is the minimum spanning tree problem. A spanning tree is a set of edges that connects all the vertices with no loop. A minimum spanning tree, shortened to MST, is a spanning tree with the lowest total edge weight. Two standard methods solve it. Prim's algorithm grows one tree outward from a starting vertex. Kruskal's algorithm sorts all the edges and adds the cheapest ones that do not form a loop.

Both methods give the same total weight. They can give different trees when two edges have the same weight, and both answers are correct. The useful question is which method is faster for your graph, and why. This lesson builds both methods, traces them on a small example, and then times them on a dense graph and a sparse graph.

The lesson uses the adjacency list from the first lesson of this module and the heap from the heaps module. Kruskal's method uses union-find, which the module covers in more depth in its later lessons. Here you only need the basic version, which is written out in full below.

Two words need a plain meaning. A dense graph has close to the most possible edges, so each vertex links to many others. A sparse graph has only a few edges per vertex, so most vertices link to only a few others. For n vertices, a complete graph has n * (n - 1) / 2 edges, which is the most a simple graph can have.

A small example

Look at five vertices numbered 0 to 4, with these weighted edges. Each line is one edge, written as two endpoints and a weight.

• 0 and 1, weight 4
• 0 and 2, weight 1
• 1 and 2, weight 2
• 1 and 3, weight 5
• 2 and 3, weight 8
• 3 and 4, weight 3
• 2 and 4, weight 9

Edges with no direction are called undirected. You can travel either way along them.

A correct answer uses four edges, because five vertices in a tree need 5 - 1 = 4 edges. The cheapest answer is edges 0-2 (1), 1-2 (2), 3-4 (3) and 1-3 (5). Its total weight is 11. The edge 0-1 is left out, because adding it would close a loop 0-1-2-0. Both algorithms should find this set of four edges, or another set with the same total.

Prim's algorithm: grow one tree

Prim's method starts with one vertex in the tree. At every step it looks at all edges that leave the tree, meaning one end is inside the tree and the other end is outside. It picks the cheapest one and adds the outside vertex to the tree. It repeats until every vertex is in the tree.

The hard part is finding the cheapest edge that leaves the tree quickly. A heap is the right tool. A heap is a structure that always gives back the smallest item it holds, and it does so in time that grows slowly with its size. In C++ the standard heap is std::priority_queue. By default it gives the largest item first, so you pass std::greater<> to make it give the smallest first.

The heap stores pairs of (weight, vertex). When a vertex joins the tree, push one entry for each edge that goes from it to a vertex outside the tree. When you pop an entry whose vertex is already in the tree, skip it. Such an entry is out of date: it came from an edge that now joins two vertices inside the tree, and adding it would create a loop.

Here is the trace on the small example, starting at vertex 0. The heap is written as a list of (weight, vertex) pairs, with the smallest first.

1. Start with heap [(0, 0)]. Pop (0, 0). Vertex 0 is not in the tree, so add it. Its edges go to 1 with weight 4 and to 2 with weight 1. Push both. Heap [(1, 2), (4, 1)]. Total 0.
2. Pop (1, 2). Add vertex 2, total 1. Its edges go to 0 (already in the tree, skip), to 1 with weight 2, to 3 with weight 8, and to 4 with weight 9. Push the three that lead outside. Heap [(2, 1), (4, 1), (8, 3), (9, 4)].
3. Pop (2, 1). Add vertex 1, total 3. Its edges go to 0 and 2 (both in the tree) and to 3 with weight 5. Push (5, 3). Heap [(4, 1), (5, 3), (8, 3), (9, 4)].
4. Pop (4, 1). Vertex 1 is already in the tree, so this entry is out of date. Skip it.
5. Pop (5, 3). Add vertex 3, total 8. Its edges go to 1 and 2 (both in the tree) and to 4 with weight 3. Push (3, 4). Heap [(3, 4), (8, 3), (9, 4)].
6. Pop (3, 4). Add vertex 4, total 11. All five vertices are in the tree, so stop.

The total is 11, which matches the answer above. Step 4 shows why the skip check matters. Without it, the out-of-date entry for vertex 1 would be added a second time.

Writing Prim's algorithm in C++

Prim's method needs each vertex's neighbours. The adjacency list stores, for each vertex, a list of the edges that leave it. Because the graph is undirected, each edge is stored twice, once from each end.

The code below uses a small helper for the union-find structure that Kruskal's method needs. It is placed here so the whole file can be compiled at once. The helper uses path halving, which means each lookup makes the path to the root shorter, and union by size, which means the smaller tree is attached under the larger one.

#include <algorithm>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
 
struct Edge {
    int from;
    int to;
    int weight;
};
 
// Adjacency list entry: where the edge goes and what it costs.
struct Neighbour {
    int to;
    int weight;
};
 
// Union-find with path halving and union by size.
class DisjointSet {
public:
    explicit DisjointSet(int n) : parent_(n), size_(n, 1) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }
    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];
            x = parent_[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size_[a] < size_[b]) std::swap(a, b);
        parent_[b] = a;
        size_[a] += size_[b];
        return true;
    }
private:
    std::vector<int> parent_;
    std::vector<int> size_;
};
 
// Prim: grow one tree from vertex 0. Returns total weight, or -1 if not connected.
long long prim(int n, const std::vector<std::vector<Neighbour>>& adj) {
    using Item = std::pair<int, int>;  // (weight, vertex)
    std::priority_queue<Item, std::vector<Item>, std::greater<>> heap;
    std::vector<bool> in_tree(n, false);
    heap.push({0, 0});
    long long total = 0;
    int added = 0;
    while (!heap.empty() && added < n) {
        auto [w, v] = heap.top();
        heap.pop();
        if (in_tree[v]) continue;
        in_tree[v] = true;
        total += w;
        ++added;
        for (const Neighbour& e : adj[v]) {
            if (!in_tree[e.to]) heap.push({e.weight, e.to});
        }
    }
    return added == n ? total : -1;
}
 
// Kruskal: sort all edges, keep each one that joins two different trees.
long long kruskal(int n, std::vector<Edge> edges) {
    std::sort(edges.begin(), edges.end(),
              [](const Edge& a, const Edge& b) { return a.weight < b.weight; });
    DisjointSet dsu(n);
    long long total = 0;
    int added = 0;
    for (const Edge& e : edges) {
        if (dsu.unite(e.from, e.to)) {
            total += e.weight;
            ++added;
        }
    }
    return added == n - 1 ? total : -1;
}
 
std::vector<std::vector<Neighbour>> to_adjacency(int n, const std::vector<Edge>& edges) {
    std::vector<std::vector<Neighbour>> adj(n);
    for (const Edge& e : edges) {
        adj[e.from].push_back({e.to, e.weight});
        adj[e.to].push_back({e.from, e.weight});
    }
    return adj;
}

The main loop of prim is the trace above written as code. The in_tree vector is the check that skips out-of-date entries. The loop also stops early once added reaches n, so the leftover heap entries are never looked at.

The function returns -1 when the graph is not connected. In that case the heap runs out before every vertex is added. A disconnected graph has no spanning tree, so there is no answer to return.

Kruskal's algorithm: sort, then join

Kruskal's method looks at the edges in order from cheapest to most expensive. For each edge, it asks one question: do its two ends already belong to the same tree? If not, the edge joins two trees, so it is safe to add. If yes, the edge would close a loop, so it is skipped.

The question is answered by union-find. Each vertex belongs to a set. find returns the set's representative (one chosen vertex that names the whole set), and unite merges two sets. Two vertices are in the same tree exactly when their find results match. A unite call that returns false means the edge would close a loop.

The trace on the small example, with the edges sorted by weight:

1. Edge 0-2 (1). The sets are different, so join them. Total 1. Edges added 1.
2. Edge 1-2 (2). Vertex 1 is in its own set and vertex 2 is in the set with 0. Join. Total 3. Edges added 2.
3. Edge 3-4 (3). Both are in their own sets. Join. Total 6. Edges added 3.
4. Edge 0-1 (4). Vertices 0 and 1 are already in one set, through 2. Skip.
5. Edge 1-3 (5). Vertex 3 is in the set with 4, and vertex 1 is in the set with 0, 1 and 2. Join. Total 11. Edges added 4, which is n - 1, so stop.

The last two edges, 2-3 (8) and 2-4 (9), are looked at and skipped, because their ends are already in one tree. Once four edges are added, the tree is complete, so the loop could stop there. The code above keeps going through the list, which is harmless.

Dense graphs and sparse graphs

Both algorithms are fast, but their costs differ. Use V for the number of vertices and E for the number of edges.

• Prim with a heap runs in about E log V time. Each edge may be pushed into the heap once from each end, and each push or pop costs about log of the heap size.
• Kruskal runs in about E log E time. Most of that time goes to sorting the edges. The union-find work is nearly constant per edge.

Since E is at most V * V, the two bounds are close in theory. The difference shows in practice. In a dense graph, E is close to V * V / 2, and Kruskal has to sort almost all of those edges. In a sparse graph, E is only a few times V, so Kruskal's sort is small, and the main cost is reading the edges once.

A second option for dense graphs is Prim with a plain array instead of a heap. The method keeps, for each vertex, the cheapest edge found so far into the tree. Each step scans all V vertices to find the smallest one, which costs V * V total with no heap at all. For a complete graph that is the same order as reading all the edges, so this version is often the best choice there.

The code below times both methods on two random graphs. The first has 2000 vertices and 1999000 edges, which is the number a complete graph would have. The edges are picked at random, so a pair can repeat and another pair can be missing, which makes it a dense random graph rather than an exact complete graph. The second has 200000 vertices and 600000 edges. Each graph starts with a random spanning tree, so it is always connected. The benchmark was compiled with g++ -std=c++20 -Wall -O2 on g++ 15.2 and run once.

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <random>
#include <utility>
#include <vector>
 
struct Edge {
    int from;
    int to;
    int weight;
};
 
struct Neighbour {
    int to;
    int weight;
};
 
class DisjointSet {
public:
    explicit DisjointSet(int n) : parent_(n), size_(n, 1) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }
    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];
            x = parent_[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size_[a] < size_[b]) std::swap(a, b);
        parent_[b] = a;
        size_[a] += size_[b];
        return true;
    }
private:
    std::vector<int> parent_;
    std::vector<int> size_;
};
 
long long prim(int n, const std::vector<std::vector<Neighbour>>& adj) {
    using Item = std::pair<int, int>;
    std::priority_queue<Item, std::vector<Item>, std::greater<>> heap;
    std::vector<bool> in_tree(n, false);
    heap.push({0, 0});
    long long total = 0;
    int added = 0;
    while (!heap.empty() && added < n) {
        auto [w, v] = heap.top();
        heap.pop();
        if (in_tree[v]) continue;
        in_tree[v] = true;
        total += w;
        ++added;
        for (const Neighbour& e : adj[v]) {
            if (!in_tree[e.to]) heap.push({e.weight, e.to});
        }
    }
    return added == n ? total : -1;
}
 
long long kruskal(int n, std::vector<Edge> edges) {
    std::sort(edges.begin(), edges.end(),
              [](const Edge& a, const Edge& b) { return a.weight < b.weight; });
    DisjointSet dsu(n);
    long long total = 0;
    int added = 0;
    for (const Edge& e : edges) {
        if (dsu.unite(e.from, e.to)) {
            total += e.weight;
            ++added;
        }
    }
    return added == n - 1 ? total : -1;
}
 
std::vector<std::vector<Neighbour>> to_adjacency(int n, const std::vector<Edge>& edges) {
    std::vector<std::vector<Neighbour>> adj(n);
    for (const Edge& e : edges) {
        adj[e.from].push_back({e.to, e.weight});
        adj[e.to].push_back({e.from, e.weight});
    }
    return adj;
}
 
int main() {
    std::vector<Edge> small = {{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {3, 4, 3}, {2, 4, 9}};
    std::cout << "small prim=" << prim(5, to_adjacency(5, small))
              << " kruskal=" << kruskal(5, small) << "\n";
 
    std::vector<Edge> disconnected = {{0, 1, 4}, {2, 3, 1}};
    std::cout << "disconnected prim=" << prim(4, to_adjacency(4, disconnected))
              << " kruskal=" << kruskal(4, disconnected) << "\n";
 
    std::mt19937 rng(42);
    auto bench = [&](int n, int m) {
        std::vector<Edge> edges;
        // A random spanning tree first, so the graph is connected.
        for (int v = 1; v < n; ++v) {
            edges.push_back({static_cast<int>(rng() % v), v, static_cast<int>(1 + rng() % 1000000)});
        }
        while (static_cast<int>(edges.size()) < m) {
            int a = rng() % n, b = rng() % n;
            if (a == b) continue;
            edges.push_back({a, b, static_cast<int>(1 + rng() % 1000000)});
        }
        auto t0 = std::chrono::steady_clock::now();
        long long p = prim(n, to_adjacency(n, edges));
        auto t1 = std::chrono::steady_clock::now();
        long long k = kruskal(n, edges);
        auto t2 = std::chrono::steady_clock::now();
        std::printf("n=%6d m=%8d  prim=%lld %.1f ms  kruskal=%lld %.1f ms\n", n, m, p,
                    std::chrono::duration<double, std::milli>(t1 - t0).count(), k,
                    std::chrono::duration<double, std::milli>(t2 - t1).count());
    };
    bench(2000, 2000 * 1999 / 2);
    bench(200000, 600000);
}

Output from one run on the machine used for this lesson:

small prim=11 kruskal=11
disconnected prim=-1 kruskal=-1
n=  2000 m= 1999000  prim=1181363 79.4 ms  kruskal=1181363 113.4 ms
n=200000 m=  600000  prim=39299904347 180.7 ms  kruskal=39299904347 33.6 ms

Both methods agree on every total, which is the main check. The times are from a single run on one machine, so they will differ on yours. The shape of the result is the useful part. The Prim timing includes building the adjacency list, which is a real cost in practice. The Kruskal timing includes the sort.

On the dense graph, Prim is faster, by about 30 percent in this run. On the sparse graph, Kruskal is about five times faster than Prim. The sparse graph has many vertices with only a few edges, so Prim's heap is busy with many small updates while Kruskal's sort is short.

Common mistakes

Using a max-heap in Prim. std::priority_queue gives the largest item first by default. If you leave out std::greater<>, Prim picks the heaviest edge that leaves the tree. The result is a tree, so nothing crashes, but the total is wrong. Here is the change, and its output on the small example:

std::priority_queue<Item> heap;  // wrong: largest weight first

max-heap prim=26

The correct total is 11. The code gave 26 because it kept adding the heaviest available edges.

Forgetting the skip check in Prim. Without if (in_tree[v]) continue;, the same vertex can be added twice. Its weight is then counted twice, and the count of added vertices goes wrong too. Keep the check, and note that it is needed because the heap can hold several entries for one vertex.

Forgetting to sort in Kruskal. Kruskal only works on edges in order of weight. If the list is left in input order, the answer uses whatever edges happen to come first. On the small example, the edges in the order they were typed give this result:

kruskal without sort=13 edges=4

The correct total is 11. The number of edges added is right, so a check on the count alone would not catch the error. Check the total weight against a known answer.

Forgetting the loop check in Kruskal. The unite call returns false when the two ends are already in one tree. If the code adds the edge's weight without checking that return value, it counts edges that would close a loop. The answer is then too large, and the tree is no longer a tree.

Not handling a disconnected graph. A graph with two islands has no spanning tree. Both functions here return -1 for it, as the output above shows. If the caller ignores that value, it may treat -1 as a valid cost. Decide what the problem wants in that case, and check for it.

Using a heap in Prim on a dense graph without thinking. The heap version does one push per edge end. A graph with 2000 vertices and 1999000 edges makes almost 4 million pushes. That is fine for this size, but the array version of Prim is the better fit when the graph is nearly complete.

Practice

Exercise 1. Run Prim from vertex 4 on the small example instead of vertex 0. What total does it give?

Show the answer

It gives 11. The total of a minimum spanning tree does not depend on the starting vertex. The tree itself may be different, but the cheapest possible total is the same.

Exercise 2. A triangle has three vertices and three edges with weights 1, 2 and 3. What does Kruskal add, and what total does it return?

Show the answer

It adds the edges with weights 1 and 2, because the edge with weight 3 would close a loop. The total is 3. The unite call for the weight 3 edge returns false, so the edge is skipped.

Exercise 3. A road network has 10000 cities and 9000 roads, and it has two separate parts that cannot reach each other. What do prim and kruskal return, and why?

Show the answer

Both return -1. A spanning tree needs a path between every pair of vertices, and two separate parts have no such path. prim ends with added smaller than n. kruskal ends with fewer than n - 1 edges added.

Exercise 4. You need the MST of a complete graph with 500 vertices, where every pair is joined by an edge. Which method would you pick, and roughly how many edges does the graph have?

Show the answer

The graph has 500 * 499 / 2 = 124750 edges. For a nearly complete graph, the array version of Prim, which scans all vertices at each step, is a good choice because it avoids sorting and avoids a heap. Kruskal would also work, but it would sort all 124750 edges first.

Exercise 5. Two edges in a graph both weigh 7. Can the two algorithms return different trees? Can they return different totals?

Show the answer

They can return different trees, because the tie can be broken either way. They cannot return different totals. Both trees are minimum spanning trees, and every minimum spanning tree has the same total weight.

Summary

• A minimum spanning tree connects every vertex with the lowest total edge weight, and it uses V - 1 edges.
• Prim grows one tree from a start vertex, using a heap to pick the cheapest edge that leaves the tree.
• Kruskal sorts the edges and adds each one that joins two different trees, using union-find to check for loops.
• Both give the same total. Ties can give different trees.
• Prim with a heap suits sparse graphs, and Kruskal's sort is often the cost to watch. For near-complete graphs, Prim with an array avoids the heap and the sort.
• Check the total against a known answer, because a missing sort or a missing skip check can still return a plausible count of edges.