C++ • GREEDY ALGORITHM Prim's Algorithm (Minimum Spanning Tree)

C++ • GREEDY ALGORITHM

Prim's Algorithm (Minimum Spanning Tree)

ALGORITHM

Prim's MST

TIME COMPLEXITY

O(V²)

SPACE COMPLEXITY

O(V)

STRATEGY

Greedy

C++ Implementation

prims_mst.cpp

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

class PrimMST
{
    int V;
    int graph[100][100];

    // Utility function to find the vertex with minimum key value
    int minKey(int key[], bool mstSet[])
    {
        int min = INT_MAX, min_index;

        for (int v = 0; v < V; v++)
            if (mstSet[v] == false && key[v] < min)
                min = key[v], min_index = v;

        return min_index;
    }

public:

    // Constructor
    PrimMST()
    {
        V = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter number of vertices: ";
        cin >> V;

        cout << "Enter adjacency matrix (" << V << " x " << V << "):\n";
        for (int i = 0; i < V; i++)
        {
            for (int j = 0; j < V; j++)
            {
                cin >> graph[i][j];
            }
        }
    }

    // Function to construct and print MST using Prim's algorithm
    void primMST()
    {
        int parent[100]; // Array to store constructed MST
        int key[100];    // Key values used to pick minimum weight edge
        bool mstSet[100]; // To represent set of vertices included in MST

        // Initialize all keys as INFINITE and mstSet[] as false
        for (int i = 0; i < V; i++)
            key[i] = INT_MAX, mstSet[i] = false;

        // Always include first 1st vertex in MST.
        key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex
        parent[0] = -1; // First node is always root of MST

        // The MST will have V vertices
        for (int count = 0; count < V - 1; count++)
        {
            // Pick the minimum key vertex from the set of vertices not yet included in MST
            int u = minKey(key, mstSet);

            // Add the picked vertex to the MST Set
            mstSet[u] = true;

            // Update key value and parent index of the adjacent vertices of the picked vertex
            for (int v = 0; v < V; v++)
            {
                // graph[u][v] is non zero only for adjacent vertices of u
                // mstSet[v] is false for vertices not yet included in MST
                // Update the key only if graph[u][v] is smaller than key[v]
                if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                    parent[v] = u, key[v] = graph[u][v];
            }
        }

        // Print the constructed MST
        cout << "Edge \tWeight\n";
        int totalWeight = 0;
        for (int i = 1; i < V; i++)
        {
            cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n";
            totalWeight += graph[i][parent[i]];
        }
        cout << "Total Weight of MST: " << totalWeight << endl;
    }
};

int main()
{
    PrimMST obj;

    obj.input();
    obj.primMST();

    return 0;
}

Sample Input

Enter number of vertices: 5
Enter adjacency matrix (5 x 5):
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0

Output

Edge 	Weight
0 - 1 	2 
1 - 2 	3 
0 - 3 	6 
1 - 4 	5 
Total Weight of MST: 16

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

#include <climits>

Includes INT_MAX to represent infinity for edge weights.

class PrimMST

Creates a class named PrimMST to encapsulate the graph and MST logic.

int graph[100][100];

Adjacency matrix representation storing edge weights (0 means no direct edge).

int minKey(...)

Finds the unvisited vertex with the smallest tentative key/weight value.

PrimMST()

Class constructor that initializes vertex count to zero.

void input()

Reads the number of vertices and the adjacency matrix from the user.

key[0] = 0; parent[0] = -1;

Starts the MST selection from vertex 0 as the root.

mstSet[u] = true;

Marks the selected minimum-weight vertex as included in the MST.

parent[v] = u, key[v] = ...

Relaxes/updates the neighbor weights if a smaller connection to the MST is found.

PrimMST obj;

Instantiates the PrimMST object and triggers the constructor.

return 0;

Signals successful program execution.

How Prim's Algorithm works: Prim's algorithm is a greedy approach to find a Minimum Spanning Tree (MST) for a weighted undirected graph. It starts with an arbitrary node, grows the spanning tree edge by edge by always picking the minimum-weight edge that connects a vertex in the MST to a vertex outside the MST, until all vertices are included.