Kako Kruskalov i Primov algoritam grade minimalno razapinjujuće stablo?

Question

Accepted Answer

**Minimalno razapinjujuće stablo (MST)** povezuje sve vrhove ponderiranog, povezanog grafa sa **minimalnom ukupnom težinom grana** i bez ciklusa. **Kruskalov** i **Primov** algoritam su dva klasična pohlepna algoritma.

## Kruskalov (sortiranje grana, union-find)

Sortiraj sve grane po težini; dodaj najjeftiniju granu koja ne pravi ciklus.

```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
```

## Primov (rast stabla sa min-gomilom)

Počni od bilo kojeg vrha; iznova dodaj najjeftiniju granu koja napušta trenutno stablo.

## Usporedba

| | Kruskalov | Primov |
|---|---------|------|
| Pristup | sortiranje grana + union-find | rast od čvora + gomila |
| Vrijeme | O(E log E) | O(E log V) |
| Najbolje za | rijetke grafove | guste grafove |

## Kada koristiti / nedostaci

Koristi MST za **mrežni dizajn** — postavljanje kabela, vodovodnih cijevi, grupiranje. Oba su pohlepna i dokazano optimalna ovdje. Kruskalov trebao union-find da efikasno izbjegne cikluse.

## Zašto je važno

MST minimizira troškove povezivanja svega — izravno primjenjivo na infrastrukturu i rasporedi mreže.

To je čist slučaj gdje je pohlepan pristup dokazano optimalan, ojačavajući pohlepno-odabirnu logiku.

Kruskalov također pokazuje union-find, strukturu sa širokim algoritmičkim dometom.

	Kruskalov	Primov
Pristup	sortiranje grana + union-find	rast od čvora + gomila
Vrijeme	O(E log E)	O(E log V)
Najbolje za	rijetke grafove	guste grafove