Minimum Spanning Tree

Concept

Imagine you are a telecom company. You have 10 cities, and you need to connect them all with fiber optic cables. You are given a massive map of 100 possible routes you could dig, each with a different dollar cost (Weight).
You must connect ALL 10 cities together using the absolute minimum total dollar cost.

You are looking for a Minimum Spanning Tree (MST).

• Spanning: It must touch every single vertex in the graph.
• Tree: It must have absolutely NO cycles. (If there is a cycle, you dug a redundant cable and wasted money!).
• Minimum: The sum of all the edge weights in the tree must be the lowest possible number.

There are two legendary algorithms to solve this: Prim’s Algorithm and Kruskal’s Algorithm.

Prim’s Algorithm

Prim’s is conceptually identical to Dijkstra’s. It uses a Min-Priority Queue and grows a single, unified tree outward from a starting node.

1. Pick a random starting city.
2. Look at all the cables connected to it. Throw them into the Min-PQ.
3. Pop the absolute cheapest cable from the PQ.
4. Does this cable connect to a city we haven’t visited yet?
   • If Yes: Buy the cable! Add it to our MST. Mark the new city as visited. Throw all the new city’s cables into the PQ.
   • If No: This cable connects back to a city we already have (it would form a cycle). Throw it in the trash!
5. Repeat until all cities are visited.

// Conceptual Prim's Algorithm
function primsMST(n: number, adjList: Map<number, [number, number][]>): number {
    const visited = new Set<number>();
    const minHeap = new MinPriorityQueue({ priority: edge => edge.cost });
    let totalCost = 0;

    // Start at city 0
    visited.add(0);
    for (let edge of adjList.get(0)!) {
        minHeap.enqueue({ target: edge[0], cost: edge[1] });
    }

    while (!minHeap.isEmpty() && visited.size < n) {
        const cheapest = minHeap.dequeue().element;

        if (visited.has(cheapest.target)) continue; // Trash it (prevents cycle)

        // Buy it!
        visited.add(cheapest.target);
        totalCost += cheapest.cost;

        // Add the new city's cables to the queue
        for (let edge of adjList.get(cheapest.target)!) {
            if (!visited.has(edge[0])) {
                minHeap.enqueue({ target: edge[0], cost: edge[1] });
            }
        }
    }

    return totalCost;
}

Kruskal’s Algorithm

Instead of growing one unified tree from a starting point, Kruskal’s Algorithm looks at the entire map at once from a god’s-eye view.

1. Throw away the Adjacency List. Take the raw array of every single edge in the world, and Sort them all by cost (cheapest to most expensive).
2. Iterate through the sorted array, starting with the absolute cheapest $1 cable in the world.
3. Buy it! (As long as it doesn’t create a cycle).
4. Move to the next cheapest cable. Buy it! (As long as it doesn’t create a cycle).
5. Stop when you have purchased exactly $V - 1$ cables (the mathematical definition of a fully connected tree).

The Catch: How do you instantly know if a random cable creates a cycle?
You MUST use a specialized data structure called Union-Find (Disjoint Set) to track which clusters of cities are connected. If the $1 cable connects two cities that are already in the same Union-Find cluster, it is a cycle, and you throw it in the trash.

Interview Questions

Q: Which algorithm is faster: Prim’s or Kruskal’s?
A: It depends on the graph.

• Kruskal’s relies on sorting the entire Edge list, so its bottleneck is $O(E \log E)$. It is exceptionally fast on Sparse Graphs (where $E$ is small).
• Prim’s uses a Priority Queue, running in $O(E \log V)$ time. It is significantly faster on Dense Graphs (where there are millions of edges, making Kruskal’s sorting phase too slow).

Q: A LeetCode problem called “Min Cost to Connect All Points” (1584) gives you an array of [x,y] coordinates, and the “cost” is the Manhattan distance between them. Which algorithm should you use?
A: Prim’s Algorithm. Because every point can mathematically connect to every other point, this is an implicitly Complete Dense Graph. Kruskal’s would require calculating the distance between every single pair, building an array of $N^2$ edges, and sorting them ($O(N^2 \log N^2)$). Prim’s explores outward dynamically, requiring vastly less overhead.