Intuition

Prim’s algorithm is a greedy algorithm for finding the Minimum Spanning Tree (MST) of a weighted undirected graph. When using an adjacency matrix, we repeatedly select the minimum-weight edge that connects a new vertex to the MST, ensuring the total cost is minimized and no cycles are formed.

Approach

  1. Initialize a key array to keep track of the minimum edge weight to each vertex, and a visited array to track which vertices are in the MST.
  2. Start from any vertex (commonly vertex 0).
  3. For each step, pick the unvisited vertex with the smallest key value and add it to the MST.
  4. Update the key values for all adjacent vertices of the newly added vertex.
  5. Repeat until all vertices are included in the MST.
  6. If all vertices are not visited at the end, the graph is not connected.

C++

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

#include <vector>
#include <climits>
using namespace std;
int primsMST(int n, vector<vector<int>>& graph) {
    vector<int> key(n, INT_MAX);
    vector<bool> vis(n, false);
    key[0] = 0;
    int cost = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int v = 0; v < n; ++v) {
            if (!vis[v] && (u == -1 || key[v] < key[u])) u = v;
        }
        if (key[u] == INT_MAX) return -1; // Not connected
        vis[u] = true;
        cost += key[u];
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] && !vis[v] && graph[u][v] < key[v]) {
                key[v] = graph[u][v];
            }
        }
    }
    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

public class Solution {
    public int primsMST(int n, int[][] graph) {
        int[] key = new int[n];
        boolean[] vis = new boolean[n];
        Arrays.fill(key, Integer.MAX_VALUE);
        key[0] = 0;
        int cost = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int v = 0; v < n; v++) {
                if (!vis[v] && (u == -1 || key[v] < key[u])) u = v;
            }
            if (key[u] == Integer.MAX_VALUE) return -1; // Not connected
            vis[u] = true;
            cost += key[u];
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !vis[v] && graph[u][v] < key[v]) {
                    key[v] = graph[u][v];
                }
            }
        }
        return cost;
    }
}

Python

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

def prims_mst(n, graph):
    key = [float('inf')] * n
    vis = [False] * n
    key[0] = 0
    cost = 0
    for _ in range(n):
        u = -1
        for v in range(n):
            if not vis[v] and (u == -1 or key[v] < key[u]):
                u = v
        if key[u] == float('inf'):
            return -1  # Not connected
        vis[u] = True
        cost += key[u]
        for v in range(n):
            if graph[u][v] != 0 and not vis[v] and graph[u][v] < key[v]:
                key[v] = graph[u][v]
    return cost

Complexity

  • ⏰ Time complexity: O(V^2) — For each of the V vertices, we scan all other vertices to find the minimum key.
  • 🧺 Space complexity: O(V^2) — For the adjacency matrix and auxiliary arrays.