Kuinka Kruskal ja Prim rakentavat minimaaliset virittävän puun?

Question

Accepted Answer

**Minimaalinen virittävä puu (MST)** yhdistää kaikki painotetun, yhtenäisen graafin kärjet **minimaalisella kokonaisreunun painolla** ilman syklejä. **Kruskal** ja **Prim** ovat kaksi klassista ahne algoritmia.

## Kruskal (lajittele reunat, union-find)

Lajittele kaikki reunat painon mukaan; lisää halvin reuna, joka ei muodosta sykliä.

```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 (kasvata puu min-keolla)

Aloita mistä tahansa kärjestä; lisää toistuvasti halvin reuna, joka poistuu nykyisestä puusta.

## Vertailu

| | Kruskal | Prim |
|---|--------|------||
| Lähestymistapa | lajittele reunat + union-find | laajenna solmusta + keko |
| Aika | O(E log E) | O(E log V) |
| Paras | harvennetut graafit | tiheät graafit |

## Milloin käyttää / Sudenkuopat

Käytä MST:tä **verkon suunnitteluun** — kaapeleiden vetäminen, vesijohdot, klusterointi. Molemmat ovat ahneita ja tässä todistettavasti optimaalisia. Kruskalissa tarvitaan union-find, jotta syklit vältetään tehokkaasti.

## Miksi sillä on merkitystä

MST minimoi kaiken yhdistämisen kustannuksen — suoraan sovellettavissa infrastruktuuriin ja verkkoasetteluun.

Se on puhdas tapaus, jossa ahne valinta on todistettavasti optimaalinen, mikä vahvistaa ahne-valinnan päättelyä.

Kruskal esittelee myös union-find:iä, rakenteen, jolla on laaja algoritminen ulottuvuus.