Algorithmus von Kruskal

Zusammenfassung

Ein Greedy-Algorithmus um Minimalen Spannbaume zu berechnen. Funktionsweise nach Kruskal: Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von $G$ (dem Graphen) die kürzeste (geringstes Kantengewicht) Kante, die mit den schon gewählten Kanten keinen Kreis bildet.

Idee Algorithmus von Kruskal

Zuerst werden die Kanten aufsteigend nach ihrem Gewicht sortiert. Danach wird über die Kanten iteriert. Wenn eine Kante zwei Knoten verbindet, welche noch nicht über durch einen Pfad vorheriger Kanten verbunden sind, wird diese Kante dem MST hinzugefügt. Als Datenstruktur bietet sich eine Union-Find-Struktur an.

Algorithmus

 1def kruskal(G, w):
 2    V, E = G
 3    n = len(V)
 4    m = len(E)
 5    ET = set()
 6    V_sets = [{i} for i in range(n)]
 7    sorted_edges = sorted(E, key=lambda e: w[e])
 8    for e in sorted_edges:
 9        v_node, w_node = e
10        i = next(i for i, s in enumerate(V_sets) if v_node in s)
11        j = next(j for j, s in enumerate(V_sets) if w_node in s)
12        if i != j:
13            V_sets[i] = V_sets[i].union(V_sets[j])
14            V_sets.pop(j)
15            ET.add(e)
16    return (V, ET)

Laufzeit

Die Laufzeit ist mit Union-Find-Struktur $\mathcal O(|E|\log|E|)=\mathcal O(|E|\log|V|)$.