Kruskal gegen Prim
In der Informatik sind die Algorithmen von Prim und Kruskal ein Greedy-Algorithmus, der einen minimalen Spannbaum für einen verbundenen gewichteten ungerichteten Graphen findet. Ein aufspannender Baum ist ein Teilgraph eines Graphen, so dass jeder Knoten des Graphen durch einen Pfad verbunden ist, der ein Baum ist. Jeder Spannbaum hat ein Gewicht, und die minimal möglichen Gewichte/Kosten aller Spannbäume sind der minimale Spannbaum (MST).
Mehr über den Algorithmus von Prim
Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník und später 1957 unabhängig vom Informatiker Robert C. Prim entwickelt. 1959 wurde er von Edsger Dijkstra wiederentdeckt. Der Algorithmus lässt sich in drei Hauptschritte gliedern:
Gegeben sei der verbundene Graph mit n Knoten und dem jeweiligen Gewicht jeder Kante, 1. Wählen Sie einen beliebigen Knoten aus dem Diagramm und fügen Sie ihn dem Baum T hinzu (der der erste Knoten sein wird)
2. Betrachten Sie die Gewichte jeder Kante, die mit den Knoten im Baum verbunden ist, und wählen Sie das Minimum aus. Fügen Sie die Kante und den Knoten am anderen Ende des Baums T hinzu und entfernen Sie die Kante aus dem Graphen. (Beliebiges auswählen, wenn zwei oder mehr Mindestwerte vorhanden sind)
3. Wiederholen Sie Schritt 2, bis n-1 Kanten zum Baum hinzugefügt wurden.
Bei dieser Methode beginnt der Baum mit einem einzelnen beliebigen Knoten und erweitert sich von diesem Knoten an mit jedem Zyklus. Damit der Algorithmus richtig funktioniert, muss der Graph also ein zusammenhängender Graph sein. Die Grundform des Prim-Algorithmus hat eine Zeitkomplexität von O(V2).
Mehr über Kruskals Algorithmus
Der von Joseph Kruskal entwickelte Algorithmus erschien 1956 in den Proceedings der American Mathematical Society. Kruskals Algorithmus kann auch in drei einfachen Schritten ausgedrückt werden.
Gegeben sei der Graph mit n Knoten und dem jeweiligen Gewicht jeder Kante, 1. Wählen Sie den Bogen mit dem geringsten Gewicht des gesamten Diagramms aus und fügen Sie es dem Baum hinzu und löschen Sie es aus dem Diagramm.
2. Wählen Sie von den verbleibenden die am wenigsten gewichtete Kante so aus, dass sie keinen Zyklus bildet. Fügen Sie die Kante zum Baum hinzu und löschen Sie sie aus dem Diagramm. (Beliebiges auswählen, wenn zwei oder mehr Mindestwerte vorhanden sind)
3. Wiederholen Sie den Vorgang in Schritt 2.
Bei dieser Methode beginnt der Algorithmus mit der am wenigsten gewichteten Kante und fährt fort, jede Kante bei jedem Zyklus auszuwählen. Daher muss der Graph im Algorithmus nicht verbunden sein. Kruskals Algorithmus hat eine Zeitkomplexität von O(logV)
Was ist der Unterschied zwischen Kruskals und Prims Algorithmus?
• Der Algorithmus von Prim wird mit einem Knoten initialisiert, während der Algorithmus von Kruskal mit einer Kante beginnt.
• Die Algorithmen von Prim erstrecken sich von einem Knoten zum anderen, während der Algorithmus von Kruskal die Kanten so auswählt, dass die Position der Kante nicht auf dem letzten Schritt basiert.
• In Prims Algorithmus muss der Graph ein verbundener Graph sein, während der Kruskal-Algorithmus auch auf nicht verbundenen Graphen funktionieren kann.
• Prims Algorithmus hat eine Zeitkomplexität von O(V2), und Kruskals Zeitkomplexität ist O(logV).
