Prim's Algorithm

Algorithm for finding the minimum spanning tree (MST) of a weighted graph

Introduction

Prim's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, connected, and undirected graph. The MST is a subset of edges that connects all vertices in the graph without any cycles and with the minimum possible total edge weight

How Prim's Algorithm Works?

1

Initialization

  • Create a priority queue that stores pairs of {weight, vertex} with the smallest weight at the top.
  • Use a inMST array to track vertices already included in the MST.
2

Start from Any Vertex

  • Push {0, starting_vertex} into the priority queue (in this case, {0, 0}).
  • Initialize ans (MST cost) to 0.
3

Repeat Until All Vertices Are Processed

  • Extract the top element from priority queuethis gives the current vertex (node) and its edge weight (weight).
  • Skip the process if node is already visited.
  • Otherwise, mark it as visited and add weight to ans.
4

Traverse All Adjacent Nodes

  • For each unvisited adjacent vertex with edge weight, push {edge_weight, vertex} into priority queue.
5

Completion

  • When the priority queue is empty, return ans as the total minimum cost of the MST.
Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6
Carousel image 7
Carousel image 8
Carousel image 9

Implementation

//prim'salgorithm.cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int prims(vector<vector<pair<int, int>>> &adjlist, vector<bool> &inMST)
{
int ans = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
while (!pq.empty())
{
    int node = pq.top().second;
    int weight = pq.top().first;
    pq.pop();
    if (inMST[node])
        continue;
    inMST[node] = 1;
    ans += weight;
    for (auto &neighbor : adjlist[node])
    {
        if (!inMST[neighbor.first])
        {
            pq.push({neighbor.second, neighbor.first}); 
        }
    }
}
return ans;
}
int main()
{
///             0----20-----3-----1-----4
///             |           |           | \      
///             5           5           2  4
///             |           |           |   \       
///             1-----1-----2           5--2--6
vector<vector<pair<int, int>>> adjlist(7);
adjlist[0].push_back({3, 20});
adjlist[0].push_back({1, 5});
adjlist[1].push_back({0, 5});
adjlist[1].push_back({2, 1});
adjlist[2].push_back({1, 1});
adjlist[2].push_back({3, 5});
adjlist[3].push_back({0, 20});
adjlist[3].push_back({2, 5});
adjlist[3].push_back({4, 1});
adjlist[4].push_back({3, 1});
adjlist[4].push_back({5, 2});
adjlist[4].push_back({6, 4});
adjlist[5].push_back({4, 2});
adjlist[5].push_back({6, 2});
adjlist[6].push_back({5, 2});
adjlist[6].push_back({4, 4});
vector<bool> inMST(7, 0);
cout << prims(adjlist, inMST);
}

Time Complexity

Time Complexity:O(E log V)
where
E=Edges,
V=Vertices

Space Complexity

For inMST array: O(V)
For Priority Queue: O(V)
Space Complexity:O(V)