We have seen multiple graph representations as Adjacency list - Graph Representation Index.

Intuition

Prim’s algorithm is a greedy algorithm for finding the Minimum Spanning Tree (MST) of a weighted undirected graph. The key idea is to always add the lowest-cost edge that connects a new vertex to the growing MST, ensuring the total cost is minimized and no cycles are formed.

Approach

  1. Start from any vertex (commonly vertex 0 or a given source).
  2. Use a min-heap (priority queue) to always select the edge with the smallest weight that connects a new vertex to the MST.
  3. Mark the new vertex as visited and add its edges to the priority queue if the other endpoint is not yet in the MST.
  4. Repeat until all vertices are included in the MST or the priority queue is empty.
  5. If all vertices are not visited at the end, the graph is not connected.

Code

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>
#include <queue>
using namespace std;
int primsMST(int n, vector<vector<pair<int, int>>>& adj) {
    vector<bool> vis(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    int cost = 0, count = 0;
    minHeap.push({0, 0}); // {cost, node}
    while (!minHeap.empty() && count < n) {
        auto [w, u] = minHeap.top(); minHeap.pop();
        if (vis[u]) continue;
        vis[u] = true;
        cost += w;
        count++;
        for (auto& [v, wt] : adj[u]) {
            if (!vis[v]) minHeap.push({wt, v});
        }
    }
    for (bool v : vis) if (!v) return -1;
    return cost;
}

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import java.util.*;
public class Solution {
    public int primsMST(int n, List<List<int[]>> adj) {
        boolean[] vis = new boolean[n];
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        int cost = 0, count = 0;
        minHeap.offer(new int[]{0, 0}); // {node, cost}
        while (!minHeap.isEmpty() && count < n) {
            int[] curr = minHeap.poll();
            int u = curr[0], w = curr[1];
            if (vis[u]) continue;
            vis[u] = true;
            cost += w;
            count++;
            for (int[] nei : adj.get(u)) {
                if (!vis[nei[0]]) {
                    minHeap.offer(new int[]{nei[0], nei[1]});
                }
            }
        }
        for (boolean v : vis) if (!v) return -1;
        return cost;
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def prims_mst(n, adj):
    import heapq
    vis = [False] * n
    min_heap = [(0, 0)]  # (cost, node)
    cost = 0
    count = 0
    while min_heap and count < n:
        w, u = heapq.heappop(min_heap)
        if vis[u]:
            continue
        vis[u] = True
        cost += w
        count += 1
        for v, wt in adj[u]:
            if not vis[v]:
                heapq.heappush(min_heap, (wt, v))
    if not all(vis):
        return -1
    return cost

Complexity

  • ⏰ Time complexity: O(E log V) — Each edge is pushed/popped from the priority queue at most once, and the queue operations take O(log V) time, where E is the number of edges and V is the number of vertices.
  • 🧺 Space complexity: O(V + E) — For the adjacency list and the priority queue.