Hur bygger Kruskal och Prim ett minimalt spännträd?

Question

Accepted Answer

Ett **minimalt spännträd (MST)** förbinder alla hörn i en viktad, sammanhängande graf med den **minimala totala kantvikten** och utan cykler. **Kruskal** och **Prim** är två klassiska giriga algoritmer.

## Kruskal (sortera kanter, union-find)

Sortera alla kanter efter vikt; lägg till den billigaste kanten som inte bildar en cykel.

```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äxa ett träd med en min-heap)

Börja från valfritt hörn; upprepa genom att lägga till den billigaste kanten som lämnar det aktuella trädet.

## Jämförelse

| | Kruskal | Prim |
|---|--------|------|
| Tillvägagångssätt | sortera kanter + union-find | växa från en nod + heap |
| Tid | O(E log E) | O(E log V) |
| Bäst för | glesa grafer | täta grafer |

## När man ska använda / fallgropar

Använd MST för **nätverksdesign** — att lägga kablar, vattenledningar, klustring. Båda är giriga och bevisligen optimala här. Kruskal behöver union-find för att effektivt undvika cykler.

## Varför det spelar roll

MST minimerar kostnaden för att koppla ihop allt — direkt tillämpligt på infrastruktur och nätverkslayout.

Det är ett rent fall där girighet är bevisligt optimal, vilket förstärker greedy-choice-resonemang.

Kruskal visar också union-find, en struktur med bred algoritmisk räckvidd.

	Kruskal	Prim
Tillvägagångssätt	sortera kanter + union-find	växa från en nod + heap
Tid	O(E log E)	O(E log V)
Bäst för	glesa grafer	täta grafer