Prim’s Algorithm for Minimum Spanning Tree (MST) Medium 0 attempts
GeeksforGeeks ↗

Prim’s Algorithm for Minimum Spanning Tree (MST)

Medium GraphBFSDFS GeeksforGeeks

Given a weighted, undirected, connected graph, return the total edge weight of its minimum spanning tree using Prim's algorithm — the technique that grows the tree one vertex at a time, always extending it with the cheapest edge that connects a new vertex to the tree built so far.

Input Format
Implement primMST(V, adj). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
V = 3
adj = [[[1,1],[2,3]],[[0,1],[2,2]],[[0,3],[1,2]]]
Output
3

Example 2

Input
V = 1
adj = [[]]
Output
0
Constraints
  • 1 <= V <= 1000
  • The graph is connected and undirected.
  • adj[u] lists [neighbor, weight] pairs; each edge appears in both endpoint lists.
  • 1 <= weight <= 10^5
Test Cases (2)
Case 1
Args: [3,[[[1,1],[2,3]],[[0,1],[2,2]],[[0,3],[1,2]]]] Expected: 3
Case 2
Args: [1,[[]]] Expected: 0
Topics
GraphBFSDFS

Prim's with Linear Minimum Selection

javascript
function primMST(V, adj) {
  const visited = Array(V).fill(false), key = Array(V).fill(Infinity);
  key[0] = 0;
  let totalWeight = 0;
  for (let count = 0; count < V; count++) {
    let u = -1;
    for (let i = 0; i < V; i++) if (!visited[i] && (u===-1 || key[i]<key[u])) u = i;
    visited[u] = true; totalWeight += key[u];
    for (const [v, w] of adj[u]) if (!visited[v] && w < key[v]) key[v] = w;
  }
  return totalWeight;
}

Time: O(V² + E) for this implementation | Space: O(V)

Saved in this browser only. Private to you.

JavaScript