Hogyan építik fel a Kruskal és Prim a minimális feszítőfát?

Question

Accepted Answer

A **minimális feszítőfa (MST)** összeköti a súlyozott, összekapcsolt gráf összes csúcsát a **minimális teljes élsúllyal** és ciklusok nélkül. A **Kruskal** és a **Prim** két klasszikus mohó algoritmus.

## Kruskal (élek rendezése, union-find)

Rendezz összes élt súly szerint; add hozzá a legolcsóbb élt, amely nem okoz ciklust.

```python
def kruskal(n, edges):                 # edges: (weight, u, v)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):      # cheapest first
        ru, rv = find(u), find(v)
        if ru != rv:                   # no cycle -> take it
            parent[ru] = rv
            mst.append((u, v, w)); total += w
    return mst, total
```

## Prim (fa növesztése min-kupaccal)

Kezd bármelyik csúcsból; ismételten add hozzá az aktuális fát elhagyó legolcsóbb élt.

## Összehasonlítás

| | Kruskal | Prim |
|---|---------|------|
| Megközelítés | élek rendezése + union-find | növesztés csomópontból + kupac |
| Idő | O(E log E) | O(E log V) |
| Legjobb | ritka gráfokhoz | sűrű gráfokhoz |

## Mikor használható / buktatók

Használd az MST-t a **hálózattervezéshez** — kábel fektetés, vízcsatorna, klaszterezés. Mindkettő mohó és itt bizonyítottan optimális. Kruskalnak union-find kell a ciklusok hatékony elkerüléséhez.

## Miért fontos

Az MST minimalizálja mindenki összekapcsolásának költségét — közvetlenül alkalmazható az infrastruktúrára és a hálózat elrendezésére.

Ez egy tiszta eset, ahol a mohó megközelítés bizonyítottan optimális, erősítve a mohó-választás logikáját.

A Kruskal szintén bemutatja az union-find-et, egy szerkezetet széles algoritmikus hatókörrel.

	Kruskal	Prim
Megközelítés	élek rendezése + union-find	növesztés csomópontból + kupac
Idő	O(E log E)	O(E log V)
Legjobb	ritka gráfokhoz	sűrű gráfokhoz