Prim's Algorithm

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?

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.

Start from Any Vertex

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

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.

Traverse All Adjacent Nodes

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

Completion

When the priority queue is empty, return ans as the total minimum cost of the MST.

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);
}

# prims_algorithm.py
import heapq

def prims_algorithm(adj_list, num_vertices):
 """
 Prim's algorithm to find Minimum Spanning Tree (MST)
 
 Args:
     adj_list: Adjacency list where adj_list[u] = [(neighbor, weight), ...]
     num_vertices: Number of vertices in the graph
 
 Returns:
     Tuple of (mst_weight, mst_edges)
 """
 if num_vertices == 0:
     return 0, []
 
 # Priority queue: (weight, vertex, parent)
 pq = [(0, 0, -1)]  # Start from vertex 0 with weight 0
 in_mst = [False] * num_vertices
 mst_weight = 0
 mst_edges = []
 
 while pq:
     weight, vertex, parent = heapq.heappop(pq)
     
     # Skip if already in MST
     if in_mst[vertex]:
         continue
     
     # Add vertex to MST
     in_mst[vertex] = True
     mst_weight += weight
     
     if parent != -1:  # Don't add edge for starting vertex
         mst_edges.append((parent, vertex, weight))
     
     # Add all adjacent vertices to priority queue
     for neighbor, edge_weight in adj_list[vertex]:
         if not in_mst[neighbor]:
             heapq.heappush(pq, (edge_weight, neighbor, vertex))
 
 return mst_weight, mst_edges

# Example usage
if __name__ == "__main__":
 # Example graph with 7 vertices
 num_vertices = 7
 adj_list = [
     [(3, 20), (1, 5)],           # 0
     [(0, 5), (2, 1)],            # 1
     [(1, 1), (3, 5)],            # 2
     [(0, 20), (2, 5), (4, 1)],   # 3
     [(3, 1), (5, 2), (6, 4)],    # 4
     [(4, 2), (6, 2)],            # 5
     [(5, 2), (4, 4)]             # 6
 ]
 
 mst_weight, mst_edges = prims_algorithm(adj_list, num_vertices)
 
 print(f"Minimum Spanning Tree Weight: {mst_weight}")
 print("MST Edges:")
 for u, v, weight in mst_edges:
     print(f"  {u} -- {v} : {weight}")

# Output: Minimum Spanning Tree Weight: 11

// prims_algorithm.js

class MinHeap {
 constructor() {
     this.heap = [];
 }
 
 push(item) {
     this.heap.push(item);
     this.heapifyUp(this.heap.length - 1);
 }
 
 pop() {
     if (this.heap.length === 0) return null;
     if (this.heap.length === 1) return this.heap.pop();
     
     const root = this.heap[0];
     this.heap[0] = this.heap.pop();
     this.heapifyDown(0);
     return root;
 }
 
 heapifyUp(index) {
     while (index > 0) {
         const parentIndex = Math.floor((index - 1) / 2);
         if (this.heap[parentIndex][0] <= this.heap[index][0]) break;
         [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
         index = parentIndex;
     }
 }
 
 heapifyDown(index) {
     while (true) {
         let smallest = index;
         const leftChild = 2 * index + 1;
         const rightChild = 2 * index + 2;
         
         if (leftChild < this.heap.length && this.heap[leftChild][0] < this.heap[smallest][0]) {
             smallest = leftChild;
         }
         if (rightChild < this.heap.length && this.heap[rightChild][0] < this.heap[smallest][0]) {
             smallest = rightChild;
         }
         if (smallest === index) break;
         
         [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
         index = smallest;
     }
 }
 
 isEmpty() {
     return this.heap.length === 0;
 }
}

function primsAlgorithm(adjList, numVertices) {
 /**
  * Prim's algorithm to find Minimum Spanning Tree (MST)
  * 
  * @param {Array} adjList - Adjacency list where adjList[u] = [[neighbor, weight], ...]
  * @param {number} numVertices - Number of vertices in the graph
  * @returns {Object} - {mstWeight, mstEdges}
  */
 if (numVertices === 0) {
     return { mstWeight: 0, mstEdges: [] };
 }
 
 // Priority queue: [weight, vertex, parent]
 const pq = new MinHeap();
 pq.push([0, 0, -1]); // Start from vertex 0 with weight 0
 
 const inMST = new Array(numVertices).fill(false);
 let mstWeight = 0;
 const mstEdges = [];
 
 while (!pq.isEmpty()) {
     const [weight, vertex, parent] = pq.pop();
     
     // Skip if already in MST
     if (inMST[vertex]) continue;
     
     // Add vertex to MST
     inMST[vertex] = true;
     mstWeight += weight;
     
     if (parent !== -1) { // Don't add edge for starting vertex
         mstEdges.push([parent, vertex, weight]);
     }
     
     // Add all adjacent vertices to priority queue
     for (const [neighbor, edgeWeight] of adjList[vertex]) {
         if (!inMST[neighbor]) {
             pq.push([edgeWeight, neighbor, vertex]);
         }
     }
 }
 
 return { mstWeight, mstEdges };
}

// Example usage
function main() {
 // Example graph with 7 vertices
 const numVertices = 7;
 const adjList = [
     [[3, 20], [1, 5]],           // 0
     [[0, 5], [2, 1]],            // 1
     [[1, 1], [3, 5]],            // 2
     [[0, 20], [2, 5], [4, 1]],   // 3
     [[3, 1], [5, 2], [6, 4]],    // 4
     [[4, 2], [6, 2]],            // 5
     [[5, 2], [4, 4]]             // 6
 ];
 
 const { mstWeight, mstEdges } = primsAlgorithm(adjList, numVertices);
 
 console.log(`Minimum Spanning Tree Weight: ${mstWeight}`);
 console.log("MST Edges:");
 for (const [u, v, weight] of mstEdges) {
     console.log(`  ${u} -- ${v} : ${weight}`);
 }
}

main();

// Output: Minimum Spanning Tree Weight: 11

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)

Prim's Algorithm

On this page