C++ Program to Find the Minimum Spanning Tree Using Prim’s Algorithm

by

Introduction

In the realm of computer science and graph theory, one of the most important problems is finding the Minimum Spanning Tree (MST) of a graph. The MST is a subset of edges in a weighted graph that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. Prim’s Algorithm is a classic greedy algorithm that efficiently finds the MST for a given graph. In this article will delve into the details of Prim’s Algorithm, presenting three real examples with distinct solutions and outputs to illustrate its application in C++.

Prerequisites

Before diving into the examples, it’s essential to have a fundamental understanding of the following concepts:

  • Graphs: A graph is a collection of nodes (vertices) and edges connecting some or all of them.
  • Weighted Graph: A graph where each edge has a numerical value (weight) associated with it.
  • Spanning Tree: A subgraph that includes all the vertices of the original graph connected with the minimum number of edges.
  • Priority Queue: A data structure used in Prim’s Algorithm to select the edge with the smallest weight efficiently.

Additionally, a basic knowledge of C++ programming, including standard libraries like <iostream>, <vector>, and <queue>, will be beneficial.

Prim’s Algorithm Overview

Prim’s Algorithm starts with a single vertex and grows the MST one edge at a time by always choosing the smallest weight edge that connects a vertex in the MST to a vertex outside the MST. The algorithm uses a priority queue to keep track of the smallest edges.

Pseudocode for Prim’s Algorithm

  1. Initialize an empty MST.
  2. Start from an arbitrary vertex.
  3. Use a priority queue to select the smallest weight edge.
  4. Add the selected edge to the MST.
  5. Repeat until all vertices are included in the MST.

Examples

Example 1: Prim’s Algorithm Using Simple Graph

Graph Representation

Consider a simple weighted graph with four vertices:

C++
     1
  (A)---(B)
   | \   |
  3|  2\ |4
   |    \|
  (C)---(D)
     5

C++ Program

C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

void primMST(vector<vector<pair<int, int>>> &graph, int V) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    vector<int> parent(V, -1);

    int src = 0;
    pq.push({0, src});
    key[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        inMST[u] = true;

        for (auto &x : graph[u]) {
            int v = x.first;
            int weight = x.second;

            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }

    for (int i = 1; i < V; ++i)
        cout << parent[i] << " - " << i << endl;
}

int main() {
    int V = 4;
    vector<vector<pair<int, int>>> graph(V);

    graph[0].push_back({1, 1});
    graph[0].push_back({2, 3});
    graph[1].push_back({0, 1});
    graph[1].push_back({3, 4});
    graph[2].push_back({0, 3});
    graph[2].push_back({3, 5});
    graph[3].push_back({1, 4});
    graph[3].push_back({2, 5});

    primMST(graph, V);

    return 0;
}

Output

C++
0 - 1
0 - 2
1 - 3

Example 2: Prim’s Algorithm Using Complex Graph

Graph Representation

Consider a more complex graph with five vertices:

C++
         2
    (A)-------(B)
   6/ | \     / |4
  (C) |  8  /   |
 10|  |5/     1 |
  (D)-------(E)
       3

C++ Program

C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

void primMST(vector<vector<pair<int, int>>> &graph, int V) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    vector<int> parent(V, -1);

    int src = 0;
    pq.push({0, src});
    key[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        inMST[u] = true;

        for (auto &x : graph[u]) {
            int v = x.first;
            int weight = x.second;

            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }

    for (int i = 1; i < V; ++i)
        cout << parent[i] << " - " << i << endl;
}

int main() {
    int V = 5;
    vector<vector<pair<int, int>>> graph(V);

    graph[0].push_back({1, 2});
    graph[0].push_back({2, 6});
    graph[0].push_back({3, 10});
    graph[1].push_back({0, 2});
    graph[1].push_back({3, 3});
    graph[1].push_back({4, 1});
    graph[2].push_back({0, 6});
    graph[3].push_back({0, 10});
    graph[3].push_back({1, 3});
    graph[3].push_back({4, 5});
    graph[4].push_back({1, 1});
    graph[4].push_back({3, 5});

    primMST(graph, V);

    return 0;
}

Output

C++
0 - 1
1 - 4
1 - 3
0 - 2

Example 3: Prim’s Algorithm Using Larger Graph

Graph Representation

Consider a larger graph with six vertices:

C++
         3       4
    (A)------(B)----(C)
   1/ |      | 2  / | 2
  (D) |   6  |    /  |
 4|  /5\     |1  /   |3
  (E)------(F)----(G)
        7      8

C++ Program

C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

void primMST(vector<vector<pair<int, int>>> &graph, int V) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    vector<int> parent(V, -1);

    int src = 0;
    pq.push({0, src});
    key[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        inMST[u] = true;

        for (auto &x : graph[u]) {
            int v = x.first;
            int weight = x.second;

            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }

    for (int i = 1; i < V; ++i)
        cout << parent[i] << " - " << i << endl;
}

int main() {
    int V = 6;
    vector<vector<pair<int, int>>> graph(V);

    graph[0].push_back({1, 3});
    graph[0].push_back({3, 1});
    graph[1].push_back({0, 3});
    graph[1].push_back({2, 4});
    graph[1].push_back({3, 6});
    graph[1].push_back({4, 5});
    graph[2].push_back({1, 4});
    graph[2].push_back({4, 2});
    graph[2].push_back({5, 2});
    graph[3].push_back({0, 1});
    graph[3].push_back({1, 6});
    graph[3].push_back({4, 7});
    graph[4].push_back({1, 5});
    graph[4].push_back({2, 2});
    graph[4].push_back({3, 7});
    graph[4].push_back({5, 8});
    graph[5].push_back({2, 2});
    graph[5].push_back({4, 8});

    primMST(graph, V);

    return 0;
}

Output

C++
0 - 3
3 - 1
1 - 2
2 - 5
2 - 4

Conclusion

Prim’s Algorithm is a powerful and efficient method to find the Minimum Spanning Tree of a graph. Through the provided examples, we’ve seen how to implement this algorithm in C++ for different types of graphs. Each example demonstrates the process of selecting the minimum weight edges to connect all vertices while avoiding cycles