Problem Statement

Given an undirected, connected, weighted graph with V vertices and E edges, your task is to find the Minimum Spanning Tree (MST) of the graph using Prim's algorithm. The MST is defined as a spanning tree that includes all V vertices and exactly V-1 edges, with the minimum possible total edge weight.

Example

Example 1:

Input: V = 4, E = 5
       edges = [
                [0, 1, 10],
                [0, 2, 6],
                [0, 3, 5],
                [1, 3, 15],
                [2, 3, 4]
               ]
Output: MST Edges = [
                     [0, 3, 5],
                     [2, 3, 4],
                     [0, 1, 10]
                    ]
       Total Weights: 19

Different Approaches

1️⃣ Prim's Algorithm

Code:

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

// Edge structure representing an edge to a vertex with a given weight.
struct Edge {
    int weight; // Weight of the edge.
    int dest;   // Destination vertex.
};

// Custom comparator for the min-priority queue.
// It ensures the edge with the smallest weight is at the top.
struct CompareEdge {
    bool operator()(const Edge &a, const Edge &b) {
        return a.weight > b.weight;
    }
};

// Prim's algorithm to compute the Minimum Spanning Tree (MST).
// 'V' is the number of vertices, and 'adj' is the adjacency list.
// Each element in the adjacency list is a pair (neighbor, weight).
vector<pair<int, int>> primMST(int V, const vector<vector<pair<int, int>>>& adj) {
    // Boolean array to mark vertices included in MST.
    vector<bool> inMST(V, false);
    // Parent array to store the MST structure (for each vertex, store the parent vertex).
    vector<int> parent(V, -1);
    // Key array to store the minimum weight edge for each vertex.
    vector<int> key(V, INF);
    
    // Min-priority queue (min-heap) that stores edges by increasing weight.
    priority_queue<Edge, vector<Edge>, CompareEdge> minHeap;
    
    // Start from vertex 0. No edge is needed to connect 0, so weight is 0.
    key[0] = 0;
    minHeap.push({0, 0});
    
    // Process until the min-heap is empty.
    while (!minHeap.empty()) {
        // Extract the edge with the minimum weight.
        int u = minHeap.top().dest;
        minHeap.pop();
        
        // If vertex 'u' is already in MST, skip it.
        if (inMST[u])
            continue;
        
        // Include vertex 'u' in the MST.
        inMST[u] = true;
        
        // For every adjacent vertex v of u, check if we can update the key.
        for (const auto &neighbor : adj[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;
            
            // If vertex v is not yet in MST and edge (u,v) is lighter than current key[v],
            // update key[v] and set u as its parent.
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
                minHeap.push({key[v], v});
            }
        }
    }
    
    // Build the MST result. We start from vertex 1 since vertex 0 is the starting point.
    vector<pair<int, int>> mstEdges;
    for (int v = 1; v < V; v++) {
        mstEdges.push_back({parent[v], v});
    }
    
    return mstEdges;
}

int main() {
    int V = 4;  // Number of vertices.
    
    // Graph represented as an adjacency list.
    // For each vertex, store pairs (neighbor, weight).
    vector<vector<pair<int, int>>> adj(V);
    
    // Adding edges for an undirected graph:
    // Edge between 0 and 1 with weight 10.
    adj[0].push_back({1, 10});
    adj[1].push_back({0, 10});
    
    // Edge between 0 and 2 with weight 6.
    adj[0].push_back({2, 6});
    adj[2].push_back({0, 6});
    
    // Edge between 0 and 3 with weight 5.
    adj[0].push_back({3, 5});
    adj[3].push_back({0, 5});
    
    // Edge between 1 and 3 with weight 15.
    adj[1].push_back({3, 15});
    adj[3].push_back({1, 15});
    
    // Edge between 2 and 3 with weight 4.
    adj[2].push_back({3, 4});
    adj[3].push_back({2, 4});
    
    // Compute the MST using Prim's algorithm.
    vector<pair<int, int>> mstEdges = primMST(V, adj);
    
    // Output the edges in the MST.
    cout << "Edges in the Minimum Spanning Tree:" << endl;
    for (auto edge : mstEdges) {
        cout << edge.first << " - " << edge.second << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:
  • Prim's algorithm initializes key, parent, and in MST arrays in O(V) time.
  • Then, for each vertex, operations on the min-priority queue (insertions and extractions) take O(log V) time.
    • Since each edge is examined during relaxation and may cause a push into the priority queue, the total time for processing edges is O(E log V). Therefore, the overall time complexity is O((V + E) log V).
• Space Complexity:
  • The adjacency list uses O(V + E) space. The auxiliary arrays (key, parent, inMST) require O(V) space, and the priority queue in the worst-case holds O(V) elements.
  • Thus, the overall space complexity is O(V + E).