Jak Kruskalův a Primův algoritmus staví minimální kostru grafu?

Question

Accepted Answer

**Minimální kostra (MST)** spojuje všechny vrcholy váženého, souvislého grafu s **minimální celkovou vahou hran** bez cyklů. **Kruskalov** a **Primův** algoritmus jsou dva klasické hladové algoritmy.

## Kruskalov algoritmus (třídění hran, union-find)

Setřiďte všechny hrany podle váhy; přidejte nejlevnější hranu, která nevytváří cyklus.

```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ův algoritmus (růst stromu s min-heap)

Začněte z libovolného vrcholu; opakovaně přidávejte nejlevnější hranu vycházející z aktuálního stromu.

## Porovnání

| | Kruskalov | Primův |
|---|--------|------||
| Přístup | třídění hran + union-find | růst z uzlu + heap |
| Čas | O(E log E) | O(E log V) |
| Nejlepší pro | řídké grafy | husté grafy |

## Kdy použít / Úskalí

Verejte MST pro **návrh sítě** — pokládání kabelů, vodovodní potrubí, shlukování. Oba jsou hladové a zde je prokázaně optimální. Kruskalov algoritmus potřebuje union-find, aby efektivně zabránil cyklům.

## Proč je to důležité

MST minimalizuje náklady na připojení všeho — přímo použitelné na infrastrukturu a návrh sítě.

Je to čistý případ, kde je hladový přístup prokázaně optimální, což posiluje hladové uvažování.

Kruskalov algoritmus také ukazuje union-find, strukturu s širokým algoritmickým dopadem.