Prim's Algorithm

Prim's algorithm is a greedy algorithm that finds a Minimum Spanning Tree (MST) for a connected, weighted, undirected graph. Unlike Kruskal's algorithm, which considers edges, Prim's algorithm grows the MST by adding vertices.

Steps of Prim's Algorithm

1. Initialize:

   • Start with an arbitrary vertex and mark it as part of the MST.
   • Use a priority queue (or min-heap) to keep track of the minimum weight edges that connect the MST to vertices outside the MST.

2. Grow the MST:

   • While there are still vertices not included in the MST:
     • Extract the edge with the smallest weight from the priority queue.
     • If the extracted edge connects a vertex not already in the MST, add it to the MST and mark the new vertex as part of the MST.
     • Add all edges connected to the newly added vertex to the priority queue.

3. Repeat until all vertices are included in the MST.

Time Complexity

• The time complexity of Prim's algorithm is O(ElogV), where E is the number of edges and V is the number of vertices, when using a priority queue implemented with a binary heap.

JavaScript Implementation

class MinMaxPriorityQueue {

  #heap = []
  #compare;

  constructor(compare) {
    this.#heap = [];
    this.#compare = compare || ((a, b) => a - b) //By default, keep it MinHeap
  }

  // Add a new element to the priority queue
  enqueue = (value) => {
    this.#heap.push(value);
    this.#heapifyUp(this.#heap.length - 1);
  }

  // Remove and return the element with the highest priority (smallest for min-heap, largest for max-heap)
  dequeue = () => {
    if (this.#heap.length === 0) return null;
    const root = this.#heap[0];
    const end = this.#heap.pop();
    if (this.#heap.length > 0) {
      this.#heap[0] = end;
      this.#heapifyDown(0);
    }
    return root;
  }

  // Peek at the element with the highest priority without removing it
  peek = () => {
    return this.#heap.length > 0 ? this.#heap[0] : null;
  }

  // Check if the priority queue is empty
  isEmpty = () => {
    return this.#heap.length === 0;
  }

  // Get the size of the priority queue
  size = () => {
    return this.#heap.length;
  }

  // Get the heap
  get heap() {
    return this.#heap
  }

  // Maintain heap property by moving element up
  #heapifyUp = (index) => {
    let parent = Math.floor((index - 1) / 2);
    while (index > 0 && this.#compare(this.#heap[index], this.#heap[parent]) < 0) {
      this.#swap(index, parent)
      index = parent;
      parent = Math.floor((index - 1) / 2);
    }
  }

  // Maintain heap property by moving element down
  #heapifyDown = (index) => {
    const length = this.#heap.length;
    let left = 2 * index + 1;
    let right = 2 * index + 2;
    let extreme = index;

    if (left < length && this.#compare(this.#heap[left], this.#heap[extreme]) < 0) {
      extreme = left;
    }

    if (right < length && this.#compare(this.#heap[right], this.#heap[extreme]) < 0) {
      extreme = right;
    }

    if (extreme !== index) {
      this.#swap(index, extreme)
      this.#heapifyDown(extreme);
    }
  }

  #swap = (i, j) => {
    [this.#heap[i], this.#heap[j]] = [this.#heap[j], this.#heap[i]]
  }
}

//Prim's Algorithm
function prim(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v, weight] of edges) {
    graph[u].push([v, weight]);
    graph[v].push([u, weight]);
  }

  const mst = [];
  const visited = new Set();
  const minHeap = new MinMaxPriorityQueue((a, b) => a[1] - b[1]); // MinHeap based on weight

  visited.add(0);
  for (const [neighbor, weight] of graph[0]) {
    minHeap.enqueue([neighbor, weight]);
  }

  while (!minHeap.isEmpty()) {
    const [u, weight] = minHeap.dequeue();
    if (visited.has(u)) continue;
    visited.add(u);
    mst.push([u, weight]);

    for (const [neighbor, edgeWeight] of graph[u]) {
      if (!visited.has(neighbor)) {
        minHeap.enqueue([neighbor, edgeWeight]);
      }
    }
  }

  return mst;
}

// Example usage
const n = 4; // Number of vertices
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

console.log(prim(n, edges)); // [ [ 3, 5 ], [ 2, 4 ], [ 1, 10 ] ]