Jak Kruskal i Prim budują minimalne drzewo rozpinające?

Question

Accepted Answer

**Minimalne drzewo rozpinające (MST)** łączy wszystkie wierzchołki ważonego, spójnego grafu o **minimalnej całkowitej wadze krawędzi** i bez cykli. **Kruskal** i **Prim** to dwa klasyczne algorytmy zachłanne.

## Kruskal (sortuj krawędzie, union-find)

Posortuj wszystkie krawędzie według wagi; dodaj najtańszą krawędź, która nie tworzy cyklu.

```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 (rozwijaj drzewo za pomocą min-heap)

Zacznij od dowolnego wierzchołka; wielokrotnie dodawaj najtańszą krawędź opuszczającą bieżące drzewo.

## Porównanie

| | Kruskal | Prim |
|---|--------|------|
| Podejście | sortuj krawędzie + union-find | rozwijaj z węzła + heap |
| Czas | O(E log E) | O(E log V) |
| Najlepsze dla | grafy rzadkie | grafy gęste |

## Kiedy użyć / pułapki

Użyj MST do **projektowania sieci** — układanie kabli, rur wodnych, grupowania. Oba są zachłanne i okazano, że są tu optymalne. Kruskal wymaga union-find, aby efektywnie unikać cykli.

## Dlaczego to ważne

MST minimalizuje koszt połączenia wszystkiego — bezpośrednio zastosowalne do infrastruktury i układu sieci.

To czysty przypadek, w którym zachłanność jest okazkowo optymalna, wzmacniając rozumowanie wyboru zachłannego.

Kruskal również prezentuje union-find, strukturę o szerokim zasięgu algorytmicznym.

	Kruskal	Prim
Podejście	sortuj krawędzie + union-find	rozwijaj z węzła + heap
Czas	O(E log E)	O(E log V)
Najlepsze dla	grafy rzadkie	grafy gęste