Kako Kruskalov in Primov algoritem zgradita minimalno razpenjujuće drevo?

Question

Accepted Answer

**Minimalno razpenjujuće drevo (MST)** povezuje vse oglišče uteženenega, povezanega grafa z **najmanjšo skupno težo robov** in brez ciklov. **Kruskal** in **Prim** sta dva klasična požrešna algoritma.

## Kruskalov algoritem (sortiranje robov, union-find)

Sortiramo vse robove po težini; dodamo najcenejši rob, ki ne tvori cikla.

```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 algoritem (rast drevesa z min-heap)

Začnemo iz katerega koli oglišča; večkrat dodamo najcenejši rob, ki zapušča trenutno drevo.

## Primerjava

| | Kruskal | Prim |
|---|--------|------|
| Pristop | sortiranje robov + union-find | rast iz vozlišča + heap |
| Čas | O(E log E) | O(E log V) |
| Najboljši za | redke grafe | goste grafe |

## Kdaj uporabiti / pasti

Uporabite MST za **zasnovo omrežja** — polaganje kabla, vodovodnih cevi, razvrščanje. Oba sta požrešna in dokazano optimalna tukaj. Kruskalov algoritem potrebuje union-find, da učinkovito izognemo ciklom.

## Zakaj je to važno

MST zmanjšuje stroške povezovanja vsega — neposredno uporabno za infrastrukturo in postavitev omrežja.

To je jasen primer, kjer je požrešnost dokazano optimalna, kar okrepi razumevanje požrešne izbire.

Kruskalov algoritem tudi predstavlja union-find, strukturo s širokimi algoritmičnimi aplikacijami.

	Kruskal	Prim
Pristop	sortiranje robov + union-find	rast iz vozlišča + heap
Čas	O(E log E)	O(E log V)
Najboljši za	redke grafe	goste grafe