Diskussion:Algorithmus von Kruskal

Ich habe die Laufzeitbetrachtung umformuliert, so dass keine Annahmen über die implementierung (Integer, Pointer...) getroffen werden. ursprünglich:

Der Trick ist, sich zu jedem Knoten die Komponente zu merken und wieviele Knoten diese enthält. Allerdings hat man nun das Problem, dies beim Einfügen einer Kante ebenfalls in konstanter Zeit zu updaten. Dies ist nur amortisiert möglich (siehe Zu jedem Knoten existiert ein Pointer auf einen Integer, welches die Größe der Komponente angibt. Knoten der selben Komponente zeigen auf die selbe Integer-Variable (und die verschiedener Komponenten auf verschiedene Variablen). Werden zwei Komponenten durch eine neue Kante verbunden, so wird der Wert der Integervariablen entsprechend erhöht und die Pointer der ehemals kleineren Komponente auf den Integer der ehemals größeren Komponente "umgebogen". Es läßt sich zeigen, daß in der Summe höchstens 2n mal (? stimmt das Jakob?) Pointer umgebogen werden müssen, so daß im Schnitt höchstens 2 Pointer umgebogen werden müssen, dieses Umbiegen amortisiert also nur konstant viel Zeit benötigt, obwohl bei einer Verschmelzung von zwei Komponenten bis zu n/2 Pointer pro Schritt umgebogen werden müssen.