Introduction

Willkommen zurück zur Serie über Graph-Algorithmen! Ein Minimum Spanning Tree (MST) (minimaler Spannbaum) verbindet jeden Knoten eines gewichteten Graphen mit dem geringstmöglichen Gesamtkantengewicht, ohne Zyklen zu bilden.

Kruskals Algorithmus baut den MST gierig (greedy) auf: Er sortiert die Kanten von der günstigsten zur teuersten und fügt jede hinzu, solange sie keinen Zyklus erzeugt. Der Trick zur schnellen Erkennung von Zyklen ist eine Datenstruktur namens Union-Find (auch bekannt als Disjoint-Set).

Der Graph ist ungerichtet und gewichtet, gegeben als n (Knoten 0 bis n - 1) und edges, ein flaches Array von Tripeln [u0, v0, w0, ...] für eine ungerichtete Kante u - v mit dem Gewicht w.

Fangen wir an!