# Minimum Spanning Tree — डेटा स्ट्रक्चर और एल्गोरिदम

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

> सभी nodes को बिना cycle के जोड़ने वाला सबसे सस्ता edges का समूह — Kruskal's या Prim's algorithm से हल होता है।

## सबको जोड़ने का सबसे सस्ता तरीका

**Minimum Spanning Tree (MST)** सभी `V` nodes को ठीक `V-1` edges से जोड़ता है, **न्यूनतम कुल weight** के साथ, और कोई cycle नहीं। सोचें: शहरों को न्यूनतम लागत पर केबल से जोड़ना।

## Kruskal's — edges क्रमबद्ध करें, union-find

सभी edges को weight से क्रमबद्ध करें। एक edge जोड़ें अगर उसके दो सिरे **अलग-अलग components** में हों (Union-Find से जांचा गया), जिससे cycle से बचा जाता है।

```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 — एक node से बढ़ाएँ

किसी भी node से शुरू करें और बार-बार वर्तमान tree से किसी नए node तक जाने वाला **सबसे सस्ता edge** जोड़ें, एक min-heap के साथ — आकार में 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 बनाम Prim

Kruskal's, `O(E log E)`, **sparse** graphs पर बेहतर है क्योंकि यह edge-by-edge काम करता है। Prim's, heap के साथ `O(E log V)`, **dense** graphs पर बेहतर है क्योंकि यह एक tree को node-by-node बढ़ाता है।