Kruskal gegen Prim
In der Informatik sind die Algorithmen von Prim und Kruskal ein gieriger Algorithmus, der einen minimalen Spannbaum für einen verbundenen gewichteten ungerichteten Graphen findet. Ein Spanning Tree ist ein Teilgraph eines Graphen, so dass jeder Knoten des Graphen durch einen Pfad verbunden ist, der ein Baum ist. Jeder Spanning Tree hat ein Gewicht, und das minimal mögliche Gewicht / die Kosten aller Spanning Tree ist das Minimum Spanning Tree (MST).
Mehr über Prims Algorithmus
Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník und 1957 unabhängig vom Informatiker Robert C. Prim entwickelt. Er wurde 1959 von Edsger Dijkstra wiederentdeckt. Der Algorithmus kann in drei Schlüsselschritten angegeben werden.
Angesichts des verbundenen Graphen mit n Knoten und dem jeweiligen Gewicht jeder Kante
1. Wählen Sie einen beliebigen Knoten aus dem Diagramm aus und fügen Sie ihn dem Baum T hinzu (der der erste Knoten sein wird).
2. Berücksichtigen 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 Diagramm. (Wählen Sie eine aus, wenn zwei oder mehr Mindestwerte vorhanden sind.)
3. Wiederholen Sie Schritt 2, bis dem Baum n-1 Kanten hinzugefügt werden.
Bei dieser Methode beginnt der Baum mit einem einzelnen beliebigen Knoten und wird von diesem Knoten mit jedem Zyklus erweitert. Damit der Algorithmus ordnungsgemäß funktioniert, muss der Graph ein verbundener Graph sein. Die Grundform des Prim-Algorithmus hat eine zeitliche Komplexität von O (V 2).
Mehr über Kruskals Algorithmus
Der von Joseph Kruskal entwickelte Algorithmus erschien 1956 im Verfahren der American Mathematical Society. Der Kruskal-Algorithmus kann auch in drei einfachen Schritten ausgedrückt werden.
Wenn der Graph mit n Knoten und dem jeweiligen Gewicht jeder Kante gegeben ist,
1. Wählen Sie den Bogen mit dem geringsten Gewicht des gesamten Diagramms aus, fügen Sie ihn dem Baum hinzu und löschen Sie ihn aus dem Diagramm.
2. Wählen Sie aus den verbleibenden Kanten die am wenigsten gewichtete Kante so aus, dass kein Zyklus entsteht. Fügen Sie die Kante zum Baum hinzu und löschen Sie sie aus dem Diagramm. (Wählen Sie eine aus, wenn zwei oder mehr Mindestwerte vorhanden sind.)
3. Wiederholen Sie den Vorgang in Schritt 2.
Bei diesem Verfahren beginnt der Algorithmus mit der am wenigsten gewichteten Kante und setzt die Auswahl jeder Kante bei jedem Zyklus fort. Daher muss im Algorithmus der Graph nicht verbunden werden. Kruskals Algorithmus hat eine zeitliche Komplexität von O (logV)
Was ist der Unterschied zwischen dem Algorithmus von Kruskal und Prim?
• Der Algorithmus von Prim wird mit einem Knoten initialisiert, während der Algorithmus von Kruskal mit einer Kante initiiert wird.
• 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.
• Im Algorithmus von prim muss der Graph ein verbundener Graph sein, während der Kruskal auch in nicht verbundenen Graphen funktionieren kann.
• Prims Algorithmus hat eine Zeitkomplexität von O (V 2) und Kruskals Zeitkomplexität ist O (logV).
