Minimum Spanning Trees

Imagine you are building a power grid for 10 cities. You have the costs to lay electrical wire between various pairs of cities (a Weighted, Undirected Graph). Your goal is to connect ALL 10 cities together using the absolute minimum total cost of wire.

This is the Minimum Spanning Tree (MST) problem.

• Spanning: It must connect all vertices together.
• Tree: It must not contain any cycles (a cycle means you wasted money building redundant wire).
• Minimum: The sum of the edge weights must be the lowest possible.

There are two incredibly famous algorithms to solve this.

1. Kruskal's Algorithm

Kruskal's is a Greedy Algorithm that relies entirely on sorting and the Disjoint Set (Union-Find) data structure.

How it Works:

1. Extract ALL edges from the graph and sort them in ascending order of their weight.
2. Iterate through the sorted edges one by one (picking the cheapest wires first).
3. Check if the edge's two nodes are already connected using UnionFind.connected(u, v).
4. If they are already connected, ignore the edge (adding it would create a cycle!).
5. If they are not connected, add the edge to the MST and merge them using UnionFind.union(u, v).
6. Stop when you have added $V - 1$ edges (a tree with V nodes always has exactly V-1 edges).

// Assuming UnionFind class from previous module exists
function kruskals(edges: {u: number, v: number, w: number}[], numVertices: number): number {
  // 1. Sort edges by weight
  edges.sort((a, b) => a.w - b.w);
  
  const uf = new UnionFind(numVertices);
  let mstCost = 0;
  let edgesAdded = 0;
  
  // 2. Iterate through sorted edges
  for (const edge of edges) {
    if (!uf.connected(edge.u, edge.v)) {
      // 3. If no cycle, add to MST
      uf.union(edge.u, edge.v);
      mstCost += edge.w;
      edgesAdded++;
      
      // Stop early if we built the complete tree
      if (edgesAdded === numVertices - 1) break;
    }
  }
  
  return mstCost;
}

• Time Complexity: $O(E \log E)$ heavily dominated by the initial sorting of the edges. The Union-Find operations take near $O(1)$ time.

2. Prim's Algorithm

While Kruskal's sorts all edges globally, Prim's algorithm starts from a single node and "grows" the MST outwards, conceptually similar to Dijkstra's algorithm.

It uses a Min-Heap (Priority Queue) to always pick the cheapest edge connecting the growing MST to a node currently outside the MST.

How it Works:

1. Pick any random starting vertex and mark it as part of the MST.
2. Add all of its connected edges to a Min-Heap.
3. Extract the cheapest edge from the Min-Heap.
4. If the edge leads to a node already in the MST, discard it (avoids cycles).
5. If the edge leads to an unvisited node, add the node to the MST, add the edge's cost to the total, and push all of the new node's edges into the Min-Heap.
6. Repeat until all vertices are visited.

function prims(graph: Map<number, {node: number, w: number}[]>, numVertices: number): number {
  const visited = new Set<number>();
  const pq = new MinPriorityQueue(); // Extracts {node, w} based on min w
  
  let mstCost = 0;
  
  // Start at an arbitrary node (e.g., node 0)
  visited.add(0);
  for (const edge of graph.get(0) || []) {
    pq.enqueue(edge, edge.w);
  }
  
  while (!pq.isEmpty() && visited.size < numVertices) {
    const edge = pq.dequeue().element;
    
    if (visited.has(edge.node)) continue; // Skip if already in MST
    
    // Add to MST
    visited.add(edge.node);
    mstCost += edge.w;
    
    // Add new neighbors to Priority Queue
    for (const nextEdge of graph.get(edge.node) || []) {
      if (!visited.has(nextEdge.node)) {
        pq.enqueue(nextEdge, nextEdge.w);
      }
    }
  }
  
  return mstCost;
}

• Time Complexity: $O(E \log V)$ using an Adjacency List and Min-Heap.

Which one to use?

• Kruskal's is generally easier to implement and performs exceptionally well on Sparse Graphs (few edges) because sorting $E$ is fast.
• Prim's performs better on Dense Graphs (many edges) because it doesn't need to globally sort a massive list of edges upfront.