# Minimum Spanning Trees — Kruskal's and Prim's Algorithms

Source: https://skills101.in/learn/dsa/dsa-minimum-spanning-tree-kruskal-prim — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

A state government wants to connect six villages with roads so that every village can reach every other one. Each possible road has a building cost. Which roads should it build to spend the **least** money? It does not need every road — just enough to connect everything. This is the **minimum spanning tree** problem. Cable TV, power lines and computer networks are planned the same way.

## 1. Spanning trees

Take a **connected, undirected, weighted** graph with V nodes.

- A **spanning tree** is a set of edges that connects **all** V nodes with **no cycle**. It always has exactly **V − 1** edges.
- A **minimum spanning tree (MST)** is a spanning tree whose total edge weight is as small as possible.

![A graph of six nodes A to F with nine weighted edges; the five green edges A-D 2, C-F 2, B-E 3, A-B 4 and C-E 4 form the minimum spanning tree with total weight 15](https://skills101.in/learn-img/dsa/mst-graph.svg)

Why no cycle? If the chosen roads contained a cycle, you could remove the most expensive road on that cycle and every village would still be connected — at a lower cost.

Note the difference from the previous lesson: a **shortest path tree** minimises the distance from **one source** to each node; an **MST** minimises the **total** weight of the network. They are often different trees.

## 2. Kruskal's algorithm

Kruskal's idea is the simplest greedy rule you could think of:

1. Sort all edges by weight, smallest first.
2. Go through them. **Take** an edge if its two ends are in **different** parts (components); **skip** it if they are already connected, because it would close a cycle.
3. Stop after taking V − 1 edges.

![Kruskal step by step on the six-node graph: take A-D 2, C-F 2, B-E 3, A-B 4 and C-E 4; skip B-D 5, E-F 5, B-C 6 and D-E 7 because each would make a cycle; total 15](https://skills101.in/learn-img/dsa/kruskal-steps.svg)

"Are u and v already connected?" is exactly what **Union-Find** answers in almost O(1) (the next lesson explains it in depth). Here is a small version inside Kruskal:

```python
def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # shorten the path as we go
            x = parent[x]
        return x

    total, used = 0, []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru != rv:                        # different parts: take it
            parent[ru] = rv
            total += w
            used.append(f"{u}-{v}")
            if len(used) == len(nodes) - 1:
                break
    return total, used

edges = [("A", "B", 4), ("A", "D", 2), ("B", "D", 5), ("B", "C", 6), ("B", "E", 3),
         ("D", "E", 7), ("C", "E", 4), ("C", "F", 2), ("E", "F", 5)]
print(kruskal("ABCDEF", edges))
```

```text
(15, ['A-D', 'C-F', 'B-E', 'A-B', 'C-E'])
```

**Cost:** sorting takes O(E log E); the Union-Find work is nearly O(E). So Kruskal is **O(E log E)**.

## 3. Why the greedy choice is safe

The proof rests on the **cut property**: split the nodes into any two groups. Among all edges that cross between the groups, the **lightest** one belongs to some MST. When Kruskal takes an edge u–v that joins two separate parts, it is the lightest edge leaving u's part (all lighter edges were already handled), so the cut property says it is safe.

Greedy does **not** work for every problem — the coin-change and knapsack lessons show counter-examples. MST is one of the cases where it is proven to work.

## 4. Prim's algorithm

Prim grows **one** tree from a start node, like a city spreading outwards:

1. Start with any node in the tree.
2. Among all edges from the tree to a node **outside** it, pick the lightest one and add that node.
3. Repeat until all nodes are in the tree.

A min-heap of `(weight, node)` pairs gives "the lightest edge leaving the tree". As in Dijkstra, we may push a node more than once and skip it when it is already in the tree.

```python
import heapq

def prim(adj, start):
    in_tree = set()
    pq = [(0, start, None)]           # (edge weight, node, came from)
    total, order = 0, []
    while pq and len(in_tree) < len(adj):
        w, u, frm = heapq.heappop(pq)
        if u in in_tree:
            continue                  # already joined by a cheaper edge
        in_tree.add(u)
        total += w
        order.append(u if frm is None else f"{frm}-{u}({w})")
        for v, wt in adj[u]:
            if v not in in_tree:
                heapq.heappush(pq, (wt, v, u))
    return total, order

edges = [("A", "B", 4), ("A", "D", 2), ("B", "D", 5), ("B", "C", 6), ("B", "E", 3),
         ("D", "E", 7), ("C", "E", 4), ("C", "F", 2), ("E", "F", 5)]
adj = {n: [] for n in "ABCDEF"}
for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))
print(prim(adj, "A"))
```

```text
(15, ['A', 'A-D(2)', 'A-B(4)', 'B-E(3)', 'E-C(4)', 'C-F(2)'])
```

Prim takes the same five edges (in a different order) and gets the same total, 15. If several edges have equal weights, there can be **more than one** MST, but every MST has the same total weight.

## 5. Kruskal in Java

```java
import java.util.*;

public class Main {
    static int[] parent;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public static void main(String[] args) {
        // nodes A..F = 0..5; each edge is {u, v, w}
        int[][] edges = {{0, 1, 4}, {0, 3, 2}, {1, 3, 5}, {1, 2, 6}, {1, 4, 3},
                         {3, 4, 7}, {2, 4, 4}, {2, 5, 2}, {4, 5, 5}};
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        parent = new int[6];
        for (int i = 0; i < 6; i++) parent[i] = i;
        int total = 0, taken = 0;
        StringBuilder sb = new StringBuilder();
        for (int[] e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru == rv) continue;
            parent[ru] = rv;
            total += e[2];
            taken++;
            sb.append((char) ('A' + e[0])).append('-').append((char) ('A' + e[1])).append(' ');
            if (taken == 5) break;
        }
        System.out.println(sb.toString().trim());
        System.out.println("total = " + total);
    }
}
```

```text
A-D C-F B-E A-B C-E
total = 15
```

`Arrays.sort` on objects is stable, so equal-weight edges keep their input order, matching the Python result.

## 6. Kruskal or Prim?

| | Kruskal | Prim (binary heap) |
|---|---|---|
| Works on | a list of edges | an adjacency list |
| Main tool | sorting + Union-Find | min-heap |
| Time | O(E log E) | O(E log V) |
| Good when | the graph is sparse, or edges come as a list | the graph is dense, or given as adjacency |

Both are correct; in interviews Kruskal is usually quicker to write. If the graph is **not connected**, Kruskal naturally gives a minimum spanning **forest** (one tree per component), while Prim from one start only covers that start's component.

## Common mistakes

- Confusing MST with shortest paths. The MST does not give the shortest route between two nodes.
- Forgetting to check that the graph is connected: if fewer than V − 1 edges are taken, no spanning tree exists.
- In Kruskal, comparing `u` and `v` directly instead of their roots `find(u)` and `find(v)`.
- In Prim, adding a node's weight again when it is popped a second time; skip nodes already in the tree.
- Applying MST algorithms to directed graphs. They are for undirected graphs.

## Quick recap

- A spanning tree connects all V nodes with V − 1 edges and no cycle; an MST has the least total weight.
- Kruskal: sort edges, take each edge joining two different components (Union-Find); O(E log E).
- Prim: grow one tree, always add the lightest edge leaving it (min-heap); O(E log V).
- Both are greedy and proven correct by the cut property; all MSTs of a graph have the same total weight.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-minimum-spanning-tree-kruskal-prim