Wie konstruieren Kruskal und Prim einen minimalen Spannbaum?

Question

Accepted Answer

Ein **minimaler Spannbaum (MST)** verbindet alle Knoten eines gewichteten, zusammenhängenden Graphen mit **minimaler Gesamtkantenbewertung** und ohne Zyklen. **Kruskal** und **Prim** sind zwei klassische Greedy-Algorithmen.

## Kruskal (Kanten sortieren, Union-Find)

Sortieren Sie alle Kanten nach Gewicht; fügen Sie die billigste Kante hinzu, die keinen Zyklus bildet.

```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 (Baum mit Min-Heap erweitern)

Beginnen Sie mit einem beliebigen Knoten; fügen Sie wiederholt die billigste Kante hinzu, die den aktuellen Baum verlässt.

## Vergleich

| | Kruskal | Prim |
|---|--------|------||
| Ansatz | Kanten sortieren + Union-Find | Von Knoten expandieren + Heap |
| Zeit | O(E log E) | O(E log V) |
| Am besten für | dünne Graphen | dichte Graphen |

## Wann verwenden / Fallstricke

Verwendung MST für **Netzwerkdesign** — Verlegung von Kabeln, Rohren, Clustering. Beide sind Greedy-Algorithmen und hier bewiesenermaßen optimal. Kruskal benötigt Union-Find, um Zyklen effizient zu vermeiden.

## Warum es wichtig ist

MST minimiert die Kosten für die Verbindung aller Elemente — direkt anwendbar auf Infrastruktur und Netzwerk-Layout.

Es ist ein klarer Fall, in dem Greedy-Algorithmen nachweislich optimal sind und die Greedy-Choice-Argumentation verstärken.

Kruskal zeigt auch Union-Find, eine Datenstruktur mit breiter algorithmischer Bedeutung.