Prim's Algorithm
Minimum Spanning Tree (MST)

Problem Statement

Given a connected, undirected, and weighted graph with V vertices and E edges, the goal is to find a Minimum Spanning Tree (MST). A Minimum Spanning Tree is a subset of the edges that connects all the vertices with the minimum possible total edge weight and without forming any cycles.

Prim's Algorithm helps us construct this MST by starting from a node and greedily choosing the next lightest edge that connects a visited node to an unvisited node.

Sometimes, the problem may also ask to return the MST edges themselves (i.e., a list of edge pairs {u, v} included in the MST).

Algorithm Steps

1. Initialize a minHeap and push the first node (weight 0, node 0).
2. Create a visited set to track included vertices.
3. Maintain a totalWeight and optionally an mstEdges list to store the MST edges.
4. While the heap is not empty and not all vertices are included:
1. Extract the edge with the smallest weight.
2. If the destination node is not visited, add it to the MST.
3. Add the edge’s weight to totalWeight.
4. Add all adjacent unvisited edges to the heap.
5. After the loop, totalWeight holds the MST cost and mstEdges (if used) contains the MST structure.

Code

function primsMST(V, adj) {
  const visited = new Array(V).fill(false);
  const minHeap = [[0, 0]]; // [weight, vertex]
  const mstEdges = [];
  let totalWeight = 0;

  while (minHeap.length) {
    minHeap.sort((a, b) => a[0] - b[0]);
    const [weight, u] = minHeap.shift();

    if (visited[u]) continue;
    visited[u] = true;
    totalWeight += weight;

    for (const [v, wt] of adj[u]) {
      if (!visited[v]) {
        minHeap.push([wt, v]);
        mstEdges.push([u, v]);
      }
    }
  }

  console.log("MST Weight:", totalWeight);
  return { totalWeight, mstEdges };
}

// Example usage
const V = 5;
const adj = [
  [[1,2], [3,6]],
  [[0,2], [2,3], [3,8], [4,5]],
  [[1,3], [4,7]],
  [[0,6], [1,8], [4,9]],
  [[1,5], [2,7], [3,9]]
];

console.log(primsMST(V, adj));