# Minimum Spanning Tree — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/minimum-spanning-tree

> The cheapest set of edges that connects all nodes with no cycles — solved by Kruskal's or Prim's algorithm.

## Cheapest way to connect everything

A **Minimum Spanning Tree (MST)** connects all `V` nodes using exactly `V-1` edges with the **smallest total weight**, and no cycles. Think: laying cable to connect cities at minimum cost.

## Kruskal's — sort edges, union-find

Sort all edges by weight. Add an edge if its two endpoints are in **different components** (checked via Union-Find), which avoids cycles.

```python
def kruskal(n, edges):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    mst_weight, count = 0, 0
    for w, u, v in sorted(edges):        # edges as (weight, u, v)
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            mst_weight += w
            count += 1
            if count == n - 1:
                break
    return mst_weight
```

## Prim's — grow from a node

Start from any node and repeatedly add the **cheapest edge** leaving the current tree to a new node, using a min-heap — similar shape to Dijkstra.

```python
import heapq

def prim(n, g, start=0):
    visited = [False] * n
    pq = [(0, start)]
    total = 0
    while pq:
        w, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        for v, wt in g[u]:
            if not visited[v]:
                heapq.heappush(pq, (wt, v))
    return total
```

## Kruskal vs Prim

Kruskal's, `O(E log E)`, shines on **sparse** graphs since it works edge-by-edge. Prim's, `O(E log V)` with a heap, shines on **dense** graphs since it grows one tree node-by-node.