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).

Examples❯

Graph (Edge List)	Vertices (V)	MST Sum	Included Edges
[(0,1,2), (0,3,6), (1,2,3), (1,3,8), (1,4,5), (2,4,7), (3,4,9)]	5	16	{0,1}, {1,2}, {1,4}, {0,3}
[(0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4)]	4	19	{0,3}, {2,3}, {0,1}
[]	0	0	[]
[(0,1,1)]	2	1	{0,1}

Solution❯

Prim's Algorithm builds the Minimum Spanning Tree (MST) by starting at any vertex and always choosing the smallest weight edge that connects a node inside the MST to one outside of it. This greedy strategy ensures that we always take the locally optimal edge and never form a cycle.

To implement Prim's Algorithm efficiently, we use a Min Heap (Priority Queue) to keep track of the next minimum-weight edge. We also maintain a visited set to avoid adding already-included vertices, and a parent list to record the edges forming the MST.

Here’s how Prim's Algorithm works step-by-step:

Start with an arbitrary node (typically node 0).
Push all its connecting edges into a min-heap.
Pop the smallest edge from the heap and add the destination node to the MST if it's not already visited.
Repeat the process until all nodes are included.

The total weight of all selected edges gives the cost of the Minimum Spanning Tree.

Algorithm Steps❯

Initialize a minHeap and push the first node (weight 0, node 0).
Create a visited set to track included vertices.
Maintain a totalWeight and optionally an mstEdges list to store the MST edges.
While the heap is not empty and not all vertices are included:

Extract the edge with the smallest weight.
If the destination node is not visited, add it to the MST.
Add the edge’s weight to totalWeight.
Add all adjacent unvisited edges to the heap.

After the loop, totalWeight holds the MST cost and mstEdges (if used) contains the MST structure.

Code

JavaScript

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));

⬅ Previous TopicMinimum Spanning Tree in Graphs

Next Topic ⮕Disjoint Set (Union-Find) with Union by Rank and Path Compression