Hvordan konstruerer Kruskal og Prim et minimalt spændingstrær?

Question

IT Interview Practice · Accepted Answer

Et **minimalt spændingstrær (MST)** forbinder alle hjørner i en vægtet, sammenhængende graf med **minimalt samlet kantvægt** og uden cyklusser. **Kruskal** og **Prim** er to klassiske grådige algoritmer.

## Kruskal (sorter kanter, union-find)

Sorter alle kanter efter vægt; tilføj den billigste kant, der ikke danner en 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 (udvid et træ med min-heap)

Start fra vilkårligt hjørne; tilføj gentagne gange den billigste kant, der forlader det aktuelle træ.

## Sammenligning

| | Kruskal | Prim |
|---|--------|------||
| Tilgang | sorter kanter + union-find | udvid fra node + heap |
| Tid | O(E log E) | O(E log V) |
| Bedst til | sparsomme grafer | tætte grafer |

## Hvornår bruges / Faldgruber

Brug MST til **netværksdesign** — at lægge kabler, vandrør, klyngedannelse. Begge er grådige og bevisligt optimale her. Kruskal har brug for union-find for effektivt at undgå cyklusser.

## Hvorfor det betyder noget

MST minimerer omkostningen ved at forbinde alt — direkte anvendelig på infrastruktur og netværkslayout.

Det er et klart tilfælde, hvor grådig valg bevisligt er optimalt, hvilket forstærker grådig-valg-ræsonnement.

Kruskal demonstrerer også union-find, en struktur med bredt algoritmisk anvendelse.

Kruskal (sorter kanter, union-find)

Prim (udvid et træ med min-heap)

Sammenligning

Hvornår bruges / Faldgruber

Hvorfor det betyder noget

Relaterede spørgsmål