Minimum Spanning Tree (MST)

[!NOTE] Imagine you are a telecom company. You need to lay cables to connect every city. The cables are expensive. How do you connect everyone using the least amount of wire?

1. The Problem: Connecting the Dots

Given a connected, weighted, undirected graph, we want to find a subgraph that:

  1. Spans all vertices (connects everyone).
  2. Is a Tree (no cycles, minimum edges).
  3. Has the Minimum total weight.

2. Prim’s Algorithm (Grow the Tree)

Similar to Dijkstra’s. Start from an arbitrary node and always add the cheapest edge that connects a visited node to an unvisited one.

  • Strategy: Greedy (Node-based).
  • Data Structure: Priority Queue.
  • Best for: Dense Graphs.

3. Kruskal’s Algorithm (Merge the Forests)

Start with no edges. Sort all edges by weight. Iterate through sorted edges and add an edge if it doesn’t form a cycle.

  • Strategy: Greedy (Edge-based).
  • Data Structure: Union-Find (Disjoint Set).
  • Best for: Sparse Graphs.

4. Interactive: The Cable Connector

Connect all the islands with the minimum cost.

  • Prim’s Mode: Starts at a node and grows.
  • Kruskal’s Mode: Picks cheapest edges globally.
Total Cost: 0 | Edges Used: 0

5. Code Implementation: Prim’s Algorithm

Java

public int primMST(int V, List<List<int[]>> adj) {
  boolean[] visited = new boolean[V];
  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // {node, weight}

  pq.add(new int[]{0, 0});
  int mstCost = 0;

  while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int u = curr[0];
    int w = curr[1];

    if (visited[u]) continue;
    visited[u] = true;
    mstCost += w;

    for (int[] edge : adj.get(u)) {
      int v = edge[0];
      int weight = edge[1];
      if (!visited[v]) {
        pq.add(new int[]{v, weight});
      }
    }
  }
  return mstCost;
}

Go

// Use container/heap for PriorityQueue
func PrimMST(V int, adj map[int][]Edge) int {
  visited := make(map[int]bool)
  pq := make(PriorityQueue, 0)
  heap.Push(&pq, &Item{node: 0, weight: 0})

  mstCost := 0
  nodesCount := 0

  for pq.Len() > 0 && nodesCount < V {
    item := heap.Pop(&pq).(*Item)
    u := item.node
    w := item.weight

    if visited[u] { continue }
    visited[u] = true
    mstCost += w
    nodesCount++

    for _, edge := range adj[u] {
      if !visited[edge.to] {
        heap.Push(&pq, &Item{node: edge.to, weight: edge.weight})
      }
    }
  }
  return mstCost
}

6. Deep Dive Strategy Lab: Minimum Spanning Tree

Intuition Through Analogy

Think of this chapter like city route planning. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?