Looking for algorithm Keywords? Try Ask4Keywords

algorithmKruskal-Algorithmus


Bemerkungen

Der Kruskal-Algorithmus ist ein gieriger Algorithmus, der verwendet wird, um den Minimum Spanning Tree (MST) eines Diagramms zu finden. Ein minimaler Spannbaum ist ein Baum, der alle Scheitelpunkte des Graphen verbindet und das minimale Gesamtgewicht der Kanten hat.

Der Algorithmus von Kruskal tut dies, indem er Kanten mit minimalem Gewicht (die nicht bereits in der MST vorhanden sind) wiederholt auswählt und sie dem Endergebnis hinzufügt, wenn die beiden mit dieser Kante verbundenen Scheitelpunkte noch nicht in der MST verbunden sind. Union - Datenstruktur suchen kann verwendet werden, um zu prüfen, ob zwei Scheitelpunkte bereits im MST verbunden sind oder nicht. Einige Eigenschaften von MST sind wie folgt:

  1. Eine MST eines Graphen mit n Knoten hat genau n-1 Kanten.
  2. Es gibt einen eindeutigen Pfad von jedem Scheitelpunkt zu jedem anderen Scheitelpunkt.

Kruskal-Algorithmus Verwandte Beispiele