Minimum Spanning Tree: Prim's Algorithm

Lesson 13 of 17 · Graphs and trees

Prim's algorithm builds a minimum spanning tree by starting from one vertex and in every step adding the cheapest edge that connects the tree to a new vertex. It resembles Dijkstra's algorithm and also uses a priority_queue.

Before you start: prerequisites – Dijkstra, priority_queue.
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++.

What is a minimum spanning tree?

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).

The MST of this graph: 1–3 (1), 2–4 (2), 4–5 (3), 1–2 (4) – in total 10.

The idea of Prim's algorithm

We divide the vertices into those in the tree and those outside it. At the beginning only vertex 1 is in the tree. In every step, out of all the edges that lead from the tree to a vertex outside the tree we choose the cheapest one and add that vertex. This greedy choice is always correct: the cheapest edge across the "border" of the tree surely belongs to some minimum tree.

Prim from vertex 1 (in step 2 the edge 3–4 (5) is more expensive than 1–2 (4))
StepThe added edgeVertices in the treeTotal
0–{1}0
11–3 (1){1, 3}1
21–2 (4){1, 2, 3}5
32–4 (2){1, 2, 3, 4}7
44–5 (3){1, 2, 3, 4, 5}10

The program

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    vector<bool> inTree(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;   // (weight, vertex)
    pq.push({0, 1});
    long long total = 0;
    int added = 0;
    while (!pq.empty()) {
        auto [w, v] = pq.top();
        pq.pop();
        if (inTree[v]) continue;           // v is already connected by a cheaper edge
        inTree[v] = true;
        total += w;
        added++;
        for (auto [u, c] : graph[v])
            if (!inTree[u]) pq.push({c, u});
    }
    if (added < n) cout << "the graph is not connected" << endl;
    else cout << total << 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

The difference from Dijkstra: into the queue we put the weight of the edge c, not the distance from the start dist[v] + c. Complexity O(m log m).

Prim or Kruskal?

PrimKruskal
The ideagrows one tree from a vertexsorts the edges and joins parts (DSU)
Neededan adjacency list, priority_queuea list of edges, sort, DSU
A dense graph (matrix)the O(n²) version without a queue is the fastestslower
A sparse graphgoodgood, often shorter to write

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: medium

Optical cables

n buildings have to be connected with optical cables. m possible cables u v c (price) are given. Print the lowest total price for all the buildings to be connected, or IMPOSSIBLE.

Example 1

Input

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

Output

6

Example 2

Input

4 2
1 2 1
3 4 1

Output

IMPOSSIBLE
Common mistakes and tips
  • An MST exists only for a connected graph – check that all n vertices have been added.
  • The weight of the edge goes into the queue, not the sum from the start (that would be Dijkstra).
  • Keep the sum of the weights in a long long.

Check your knowledge

Open the quiz

Prim's algorithm

1. How many edges does the minimum spanning tree of a graph with n vertices have?




2. Which edge does Prim add in every step?




3. How does Prim differ from Dijkstra?