Prim's Algorithm

Prim's Algorithm

Welcome to Prim's Algorithm, a classic greedy algorithm used to find a Minimum Spanning Tree (MST) for a weighted, undirected graph. An MST is a subset of the edges that connects all the vertices together, without any cycles, and with the minimum possible total edge weight.

---

1. The Core Idea: Growing a Tree

Prim's algorithm builds an MST by starting with an arbitrary vertex and "growing" the tree one edge at a time. At each step, it greedily chooses the cheapest edge that connects a vertex in the growing MST to a vertex outside the MST.

This is very similar to Dijkstra's algorithm, but instead of tracking the total distance from the source, the priority queue stores the weight of the edge required to add a vertex to the tree.

---

2. The Algorithm Step-by-Step

1. Initialization:

   • Choose a starting vertex (it can be any vertex).
   • Create a visited set or array to mark vertices that are part of the MST.
   • Create a min-priority queue to store edges that connect the MST to outside vertices. The priority will be the edge weight.
   • Add the starting vertex to the visited set.
   • Add all its adjacent edges to the priority queue.

2. Building the MST:

   • While the priority queue is not empty and the MST doesn't yet include all vertices:
     • Extract Min Edge: Remove the edge with the smallest weight from the priority queue. Let this edge connect vertex u (in the MST) to vertex v (outside the MST).
     • If v is already in the MST, skip it and continue.
     • Add to MST: Add the edge (u, v) to our MST. Mark v as visited.
     • Add New Edges: For each neighbor w of v, add the edge (v, w) to the priority queue if w is not yet in the MST.

3. Completion:

   • The algorithm terminates when N-1 edges have been added to the MST, connecting all N vertices.

---

3. Implementation with a Priority Queue

// Assumes a MinPriorityQueue class is available
function prims(adj, startNode = 0) {
  const N = adj.length;
  const inMST = new Set();
  const mstEdges = [];
  let totalCost = 0;
  const pq = new MinPriorityQueue({ priority: (item) => item.priority });

  // Start with the first node
  inMST.add(startNode);
  for (const { neighbor, weight } of adj[startNode]) {
    pq.enqueue({ from: startNode, to: neighbor, priority: weight });
  }

  while (!pq.isEmpty() && inMST.size < N) {
    const { from, to, priority: weight } = pq.dequeue();

    if (inMST.has(to)) {
      continue;
    }

    // Add the new edge and vertex to the MST
    inMST.add(to);
    mstEdges.push({ from, to, weight });
    totalCost += weight;

    // Add the new vertex's edges to the priority queue
    for (const { neighbor, weight: newWeight } of adj[to]) {
      if (!inMST.has(neighbor)) {
        pq.enqueue({ from: to, to: neighbor, priority: newWeight });
      }
    }
  }

  return { mstEdges, totalCost };
}

---

4. Complexity Analysis

• Time Complexity: O(M log N) with a binary heap-based priority queue, where N is the number of vertices and M is the number of edges. The log N factor comes from the priority queue operations.
• Space Complexity: O(N + M) to store the adjacency list, visited set, and the priority queue.

---

Key Takeaway: Prim's algorithm is a greedy method for building a Minimum Spanning Tree. It's like Dijkstra's but focuses on edge weights rather than total path cost. It efficiently finds the cheapest set of edges to connect a graph, making it ideal for network design and other optimization problems.