Prim’s Algorithm for Minimum Spanning Tree (MST) Explained with Real-Life Example | Step-by-Step Guide

Introduction

In graph theory, one of the most important optimization problems is finding a Minimum Spanning Tree (MST). A Minimum Spanning Tree connects all vertices in a weighted graph while ensuring the total edge cost is minimum and no cycles exist.

Among the classical algorithms used to solve this problem, Prim’s Algorithm is one of the most efficient and widely used approaches, especially for dense graphs.

Prim’s Algorithm is a greedy algorithm that builds the MST incrementally, starting from a single vertex and continuously adding the smallest possible edge that expands the tree.

What is a Minimum Spanning Tree (MST)?

A spanning tree of a graph is a subgraph that:

• Connects all vertices
• Contains no cycles
• Has exactly V − 1 edges (where V is number of vertices)

A Minimum Spanning Tree (MST) is the spanning tree with the minimum total edge weight.

Key properties:

• Covers all nodes
• No cycles allowed
• Minimum total cost
• Always has V − 1 edges

What is Prim’s Algorithm?

Prim’s Algorithm is a greedy approach used to find MST in a weighted, undirected graph.

Core idea:

Start from any node and repeatedly add the minimum weight edge that connects a visited vertex to an unvisited vertex.

Why is Prim’s Algorithm Important?

Prim’s Algorithm is widely used in:

• Network design (LAN, WAN)
• Road construction planning
• Electrical grid optimization
• Computer networking
• Circuit design

It helps reduce cost while ensuring full connectivity.

Real-Life Scenario: Smart City Road Construction

Imagine a government planning to connect multiple cities with roads:

Cities:

• Lahore
• Faisalabad
• Multan
• Islamabad
• Sahiwal

Each possible road has a construction cost.

The goal is:

Connect all cities with minimum construction cost without building unnecessary roads.

This is exactly an MST problem, solved using Prim’s Algorithm.

How Prim’s Algorithm Works (Step-by-Step)

Let’s understand it clearly.

Step 1: Initialize

• Pick any starting node (e.g., Lahore)
• Mark it as visited
• MST set = empty

Step 2: Select Minimum Edge

Find the smallest edge from visited nodes to unvisited nodes.

Step 3: Add Edge to MST

Include the edge if it connects a new vertex.

Step 4: Repeat

Repeat until all vertices are included.

Example Graph (Conceptual)

Assume the following weighted connections:

• Lahore – Faisalabad = 4
• Lahore – Multan = 2
• Faisalabad – Multan = 5
• Faisalabad – Islamabad = 10
• Multan – Sahiwal = 3
• Sahiwal – Islamabad = 6

Prim’s Algorithm Execution

Start from Lahore

Visited: {Lahore}

Step 1

Choose smallest edge from Lahore:

• Lahore → Multan (2)

Visited: {Lahore, Multan}

Step 2

Check all edges from visited nodes:

• Multan → Sahiwal (3)

Visited: {Lahore, Multan, Sahiwal}

Step 3

Next smallest:

• Lahore → Faisalabad (4)

Visited: {Lahore, Multan, Sahiwal, Faisalabad}

Step 4

Next smallest:

• Sahiwal → Islamabad (6)

Visited: {All cities}

Final MST Cost

Total cost = 2 + 3 + 4 + 6 = 15

Data Structures Used in Prim’s Algorithm

Prim’s Algorithm typically uses:

1. Priority Queue (Min Heap)

Used to get the smallest edge quickly.

2. Visited Array

Tracks visited vertices.

3. Adjacency List / Matrix

Stores graph representation.

Pseudocode of Prim’s Algorithm

1. Initialize all keys = ∞
2. Set key[start] = 0
3. Insert all nodes into priority queue

4. While queue is not empty:
Extract node with minimum key

Mark node as visited

For each adjacent node:
    If edge weight < key[neighbor]:
        Update key[neighbor]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

void primMST(vector<vector<pii>>& graph, int V) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    vector<int> key(V, 1e9);
    vector<bool> inMST(V, false);

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

    int totalCost = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue;

        inMST[u] = true;
        totalCost += key[u];

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

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

    cout << "Minimum Cost of MST: " << totalCost << endl;
}

int main() {
    int V = 5;

    vector<vector<pii>> graph(V);

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

    graph[0].push_back({2, 2});
    graph[2].push_back({0, 2});

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

    graph[1].push_back({3, 10});
    graph[3].push_back({1, 10});

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

    graph[4].push_back({3, 6});
    graph[3].push_back({4, 6});

    primMST(graph, V);

    return 0;
}

Time Complexity of Prim’s Algorithm

Using Min Heap:

• O(E log V)

Where:

• E = number of edges
• V = number of vertices

Using adjacency matrix:

• O(V²)

Prim’s Algorithm vs Kruskal Algorithm

Advantages of Prim’s Algorithm

• Efficient for dense graphs
• Simple greedy approach
• Works well with adjacency matrix
• Always produces optimal MST

Disadvantages

• Not ideal for sparse graphs
• Requires priority queue implementation
• Slightly complex than Kruskal for beginners

Real-World Applications

Prim’s Algorithm is used in:

1. Internet Network Design

Connecting routers with minimum cable cost

2. Road Construction

Planning cheapest road networks

3. Electrical Grids

Designing efficient power distribution systems

4. Computer Networks

LAN/WAN optimization

5. Circuit Design

Reducing wiring cost in chips

Common Interview Questions

1. What is Prim’s Algorithm?

A greedy algorithm used to find MST by expanding from a starting node.

2. Does Prim’s Algorithm guarantee MST?

Yes, it always produces optimal MST.

3. What is the main difference between Prim and Kruskal?

Prim grows from a node, Kruskal selects edges globally.

Conclusion

Prim’s Algorithm is one of the most fundamental graph algorithms in computer science. It demonstrates how greedy strategies can efficiently solve complex optimization problems like network design.

By starting from a single node and expanding the MST step by step, Prim’s Algorithm ensures:

• Minimum cost
• Full connectivity
• No cycles

For students of data structures and algorithms, mastering Prim’s Algorithm is essential for exams, interviews, and competitive programming.