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

Prim’s Algorithm for Minimum Spanning Tree (MST)

Medium GraphBFSDFS GeeksforGeeks

Implement Prim's algorithm to find the Minimum Spanning Tree of a weighted undirected graph.

Example: V=5, edges with weights → MST with minimum total weight

Sample Input
—
Sample Output
—
Constraints
  • 2 <= V <= 1000
  • 1 <= E <= V*(V-1)/2
  • 1 <= weight <= 10^5
Topics
GraphBFSDFS

Prim's with Priority Queue

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²) or O(E log V) with heap | Space: O(V)

Saved in this browser only. Private to you.

JavaScript