Prim's Algorithm

Prim's Algorithm for Minimum Spanning Tree (MST)

Prim's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected graph with weighted edges. The MST is a tree that spans all the vertices in the graph and has the minimum possible sum of edge weights.

Overview of Prim's Algorithm:

Given a weighted graph, Prim’s algorithm builds the MST step by step, starting from an arbitrary node and adding the cheapest edge that connects a vertex in the tree to a vertex outside the tree.

Steps of Prim's Algorithm:

1. Initialize:

   • Choose an arbitrary starting vertex and mark it as part of the MST.
   • Set the initial key value for all vertices except the start vertex to infinity, and the key value of the start vertex to 0.
   • Maintain a priority queue (or a min-heap) to efficiently extract the vertex with the smallest key value.

2. Iterate:

   • Extract the vertex u with the smallest key value from the priority queue.
   • For each adjacent vertex v of u, if v is not yet included in the MST and the weight of edge (u, v) is smaller than the current key value of v, update the key value of v.

3. Repeat the above step until all vertices are included in the MST.

4. Terminate when all vertices are included in the MST, and the sum of the edges included will be the weight of the MST.

Greedy Choice:

At each step, the algorithm picks the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST, ensuring that no cycles are formed.

Time Complexity:

• Using a priority queue (min-heap), the algorithm runs in O(E log V) time, where:
  • V is the number of vertices.
  • E is the number of edges.
• With an adjacency list representation, the algorithm performs efficiently even for dense graphs.

Prim's Algorithm - Detailed Explanation:

Let’s break down the working of Prim’s algorithm using a simple example:

Example:

Consider a graph with 5 vertices and the following edges with weights:

(0)---2---(1)
 |         |
 6         3
 |         |
(2)---8---(3)
 |         
 5         
 |         
(4)

• Vertices: {0, 1, 2, 3, 4}
• Edges and their weights: (0, 1, 2), (0, 2, 6), (1, 3, 3), (2, 3, 8), (2, 4, 5)

We will use Prim's algorithm to find the MST for this graph.

Steps in Prim's Algorithm:

1. Start with Vertex 0:

   • Initialize: key[0] = 0, and key[i] = ∞ for all other vertices.
   • Initialize: parent[i] = null for all vertices.
   • Include vertex 0 in the MST.

2. Select Vertex 0:

   • From vertex 0, the available edges are (0, 1, 2) and (0, 2, 6).
   • The edge with the minimum weight is (0, 1, 2).
   • Include vertex 1 in the MST and update key[1] = 2 (since it has a smaller weight than ∞).
   • Update parent[1] = 0.

3. Select Vertex 1:

   • From vertex 1, the available edges are (1, 3, 3).
   • The edge with the minimum weight is (1, 3, 3).
   • Include vertex 3 in the MST and update key[3] = 3.
   • Update parent[3] = 1.

4. Select Vertex 3:

   • From vertex 3, the available edges are (3, 2, 8) and (3, 4, 5).
   • The edge with the minimum weight is (3, 4, 5).
   • Include vertex 4 in the MST and update key[4] = 5.
   • Update parent[4] = 3.

5. Select Vertex 4:

   • From vertex 4, the available edge is (4, 2, 5).
   • The edge with the minimum weight is (4, 2, 5).
   • Include vertex 2 in the MST and update key[2] = 5.
   • Update parent[2] = 4.

6. Finish:

   • All vertices are now included in the MST.
   • The final MST consists of the edges:
     • (0, 1, 2)
     • (1, 3, 3)
     • (3, 4, 5)
     • (4, 2, 5)

Final MST:

The MST for the given graph includes the edges:

(0, 1, 2)
(1, 3, 3)
(3, 4, 5)
(4, 2, 5)

The total weight of the MST is 2 + 3 + 5 + 5 = 15.

C++ Code for Prim's Algorithm:

Here’s a C++ implementation of Prim’s Algorithm using a priority queue to efficiently extract the minimum key value.

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

using namespace std;

struct Edge {
    int vertex, weight;
};

struct MinHeapNode {
    int vertex, key;
    
    bool operator>(const MinHeapNode& other) const {
        return key > other.key;
    }
};

void primsAlgorithm(int V, const vector<vector<Edge>>& adjList) {
    // Initialize key values as infinity and parent array to store MST
    vector<int> key(V, INT_MAX);
    vector<int> parent(V, -1);
    vector<bool> inMST(V, false);  // Track vertices included in MST
    
    // Priority queue to get the vertex with the minimum key value
    priority_queue<MinHeapNode, vector<MinHeapNode>, greater<MinHeapNode>> pq;
    
    // Start with the first vertex (vertex 0)
    key[0] = 0;
    pq.push({0, 0});  // {vertex, key}
    
    while (!pq.empty()) {
        // Get the vertex with the minimum key value
        int u = pq.top().vertex;
        pq.pop();
        
        // Include the vertex in MST
        inMST[u] = true;
        
        // Explore all adjacent vertices of u
        for (const Edge& edge : adjList[u]) {
            int v = edge.vertex;
            int weight = edge.weight;
            
            // If v is not in MST and weight of (u, v) is smaller than key[v]
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
                pq.push({v, key[v]});
            }
        }
    }
    
    // Print the MST
    cout << "Edges in MST:" << endl;
    for (int i = 1; i < V; ++i) {
        cout << parent[i] << " - " << i << " : " << key[i] << endl;
    }
}

int main() {
    int V = 5;  // Number of vertices
    vector<vector<Edge>> adjList(V);
    
    // Add edges: (u, v, weight)
    adjList[0].push_back({1, 2});
    adjList[0].push_back({2, 6});
    adjList[1].push_back({0, 2});
    adjList[1].push_back({3, 3});
    adjList[2].push_back({0, 6});
    adjList[2].push_back({3, 8});
    adjList[2].push_back({4, 5});
    adjList[3].push_back({1, 3});
    adjList[3].push_back({2, 8});
    adjList[3].push_back({4, 5});
    adjList[4].push_back({2, 5});
    adjList[4].push_back({3, 5});
    
    // Call Prim's Algorithm to find the MST
    primsAlgorithm(V, adjList);
    
    return 0;
}

Explanation of the Code:

1. Data Structures:

   • The Edge structure holds the vertex and the weight of an edge.
   • The MinHeapNode structure is used to store a vertex and its key value, which is used in the priority queue.

2. Algorithm:

   • Start from vertex 0 and initialize its key to 0.
   • Use a priority queue to select the vertex with the minimum key value.
   • For each adjacent vertex, check if it can be added to the MST by comparing the current edge weight with the existing key.
   • After processing all vertices, the MST is formed.

3. Output:

   • The program prints the edges included in the MST along with their weights.

Time Complexity:

• **O