Prim's Algorithm: Finding Minimum Spanning Trees

Introduction

Prim's Algorithm is a classic "Greedy Algorithm" used to find the Minimum Spanning Tree (MST) of 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.

What is a Minimum Spanning Tree (MST)?

Imagine a network of cities connected by roads. You want to build a network that connects every city, but you want to spend the least amount of money on road construction. The set of roads you choose that connects all cities with the minimum total cost is the MST.

The Greedy Approach

The core philosophy of Prim's Algorithm is the Greedy Approach. At each step, the algorithm makes the locally optimal choice in the hope of finding a global optimum. In Prim's case, it always picks the edge with the smallest weight that connects a vertex in the current tree to a vertex outside the tree.

Key Concepts

1. Spanning Tree

A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree (acyclic and connected).

2. Minimum Spanning Tree (MST)

A spanning tree with the minimum possible total edge weight.

3. Connected Graph

A graph where there is a path between every pair of vertices. Prim's Algorithm requires the graph to be connected; otherwise, it will only find the MST for one connected component.

How Prim's Algorithm Works

Data Structures Required

Adjacency List: To store the graph and efficiently traverse neighbors of a vertex.
Min-Heap (Priority Queue): To efficiently retrieve the edge with the smallest weight that connects the visited set to the unvisited set.

Step-by-Step Process

Initialization: Start with any arbitrary node (let's say node 0). Add this node to the visited set. Add all edges connected to this node into the Min-Heap.
Selection: Extract the edge with the minimum weight from the Min-Heap.
Validation: Check if the destination vertex of this edge is already in the visited set.

If Yes: This edge creates a cycle. Discard it and repeat step 2.
If No: This edge is part of the MST. Add the destination vertex to the visited set and add this edge to the MST.

Expansion: Add all edges from the newly visited vertex to the Min-Heap.
Repeat: Continue steps 2-4 until the Min-Heap is empty (all vertices are visited).

Complexity Analysis

Time Complexity

The time complexity of Prim's Algorithm depends heavily on the data structure used for the priority queue.

Using a Binary Heap: $O(E \log V)$
We process each edge once ($O(E)$).
Each heap operation (insert and extract-min) takes $O(\log V)$.
Using a Fibonacci Heap: $O(E + V \log V)$
This is theoretically faster for dense graphs but more complex to implement.

Space Complexity

$O(V + E)$

We store the graph in an adjacency list ($O(V + E)$).
We store the visited set ($O(V)$).
We store the Min-Heap ($O(E)$ in the worst case).

Code Implementation (TypeScript)

interface Edge {
  to: number;
  weight: number;
}

interface Graph {
  vertices: number;
  adjacencyList: Edge[][];
}

class MinHeap {
  heap: { node: number; weight: number }[];

  constructor() {
    this.heap = [];
  }

  insert(node: number, weight: number) {
    this.heap.push({ node, weight });
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index: number) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex].weight <= this.heap[index].weight) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMin(): { node: number; weight: number } | null {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const end = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown(0);
    }
    return min;
  }

  sinkDown(index: number) {
    const length = this.heap.length;
    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let swapIndex: number | null = null;

      if (leftChildIndex < length && this.heap[leftChildIndex].weight < this.heap[index].weight) {
        swapIndex = leftChildIndex;
      }

      if (
        rightChildIndex < length &&
        (swapIndex === null || this.heap[rightChildIndex].weight < this.heap[swapIndex!].weight)
      ) {
        swapIndex = rightChildIndex;
      }

      if (swapIndex === null) break;
      [this.heap[index], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[index]];
      index = swapIndex;
    }
  }
}

function primsAlgorithm(graph: Graph, startNode: number): number {
  const visited = new Set<number>();
  const minHeap = new MinHeap();
  let totalWeight = 0;

  visited.add(startNode);

  // Add all edges of the start node to the heap
  graph.adjacencyList[startNode].forEach((edge) => {
    minHeap.insert(edge.to, edge.weight);
  });

  while (minHeap.heap.length > 0) {
    const { node: current, weight } = minHeap.extractMin()!;

    if (visited.has(current)) continue;

    visited.add(current);
    totalWeight += weight;

    // Add neighbors of the newly visited node
    graph.adjacencyList[current].forEach((edge) => {
      if (!visited.has(edge.to)) {
        minHeap.insert(edge.to, edge.weight);
      }
    });
  }

  return totalWeight;
}

// Example Usage
const myGraph: Graph = {
  vertices: 4,
  adjacencyList: [
    [{ to: 1, weight: 1 }, { to: 2, weight: 4 }], // 0
    [{ to: 0, weight: 1 }, { to: 2, weight: 2 }, { to: 3, weight: 6 }], // 1
    [{ to: 0, weight: 4 }, { to: 1, weight: 2 }, { to: 3, weight: 3 }], // 2
    [{ to: 1, weight: 6 }, { to: 2, weight: 3 }], // 3
  ],
};

console.log(primsAlgorithm(myGraph, 0)); // Output: 6 (Edges: 0-1, 1-2, 2-3)

Prim's vs. Kruskal's Algorithm

Both algorithms solve the MST problem, but they differ in their approach and efficiency based on graph density.

| Feature | Prim's Algorithm | Kruskal's Algorithm |

| :--- | :--- | :--- |

| Approach | Greedy, builds tree incrementally from a starting node. | Greedy, sorts all edges and adds them if they don't form a cycle. |

| Data Structures | Adjacency List + Min-Heap. | Edge List + Union-Find (Disjoint Set). |

| Best For | Dense Graphs (where $E \approx V^2$). | Sparse Graphs (where $E \ll V^2$). |

| Time Complexity | $O(E \log V)$ | $O(E \log E)$ or $O(E \log V)$ |

Common Mistakes to Avoid

Not Handling Disconnected Graphs: If the input graph is disconnected, the algorithm will only return the MST for the connected component containing the starting node. Always check if the number of visited vertices equals the total number of vertices.
Ignoring Cycles: The algorithm relies on the visited set to skip edges that would form a cycle. Forgetting to check this will result in incorrect weights or infinite loops.
Wrong Priority Queue: Using a standard array or list for the priority queue will result in $O(V^2)$ time complexity, which is inefficient for large graphs. Always use a Min-Heap.

Real-World Applications

Network Design: Designing a network of computers or cables where you want to minimize the cost of connecting all nodes (e.g., telephone lines, fiber optics).
Circuit Design: Minimizing the length of wires needed to connect components on a circuit board.
Clustering: In machine learning, MSTs are used in algorithms like Single Linkage Clustering to group data points based on distance.
Approximation Algorithms: Prim's algorithm is used as a subroutine in approximation algorithms for the Traveling Salesman Problem (TSP) and the Metric TSP.

Summary

Prim's Algorithm is a powerful tool for finding Minimum Spanning Trees. By leveraging a greedy strategy and a Min-Heap, it efficiently connects all nodes in a graph with the least cost. Understanding the difference between dense and sparse graphs is crucial for choosing between Prim's and Kruskal's algorithms.