Unterschied zwischen Kruskal und Prim

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 Spannbaum ist ein Untergraph eines Diagramms, bei dem jeder Knoten des Diagramms durch einen Pfad verbunden ist, der ein Baum ist. Jeder überspannende Baum hat ein Gewicht und die minimal möglichen Gewichte / Kosten aller überspannenden Bäume sind die minimalen überspannenden Bäume (MST)..

Mehr über den Algorithmus von Prim

Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník und später vom Informatiker Robert C. Prim im Jahr 1957 selbstständig entwickelt. Er wurde 1959 von Edsger Dijkstra wiederentdeckt. Der Algorithmus lässt sich in drei Schritten beschreiben.

Gegeben sei der verbundene Graph mit n Knoten und der jeweiligen Kantengewichtung,

1. Wählen Sie einen beliebigen Knoten aus dem Diagramm aus und fügen Sie ihn dem Baum T hinzu (der erste Knoten).

2. Berücksichtigen Sie die Gewichtung jeder Kante, die mit den Knoten in der Baumstruktur 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. (Wählen Sie ein beliebiges, wenn zwei oder mehr Minima vorhanden sind.)

3. Wiederholen Sie Schritt 2, bis der Baum n-1 Kanten hinzugefügt wird.

Bei dieser Methode beginnt der Baum mit einem einzelnen beliebigen Knoten und wird mit jedem Zyklus von diesem Knoten aus erweitert. Damit der Algorithmus ordnungsgemäß funktioniert, muss der Graph ein zusammenhängender Graph sein. Die Grundform des Prim-Algorithmus hat eine zeitliche Komplexität von O (V²).

Mehr über den Algorithmus von Kruskal

Der von Joseph Kruskal entwickelte Algorithmus erschien 1956 in den Arbeiten der American Mathematical Society. Der Algorithmus von Kruskal 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 der geringsten Gewichtung des gesamten Diagramms aus, fügen Sie der Baumstruktur hinzu und löschen Sie ihn aus dem Diagramm.

2. Wählen Sie aus den verbleibenden Kanten die am wenigsten gewichtete Kante auf eine Weise aus, die keinen Zyklus bildet. Fügen Sie dem Baum den Rand hinzu und löschen Sie ihn aus dem Diagramm. (Wählen Sie ein beliebiges, wenn zwei oder mehr Minima vorhanden sind.)

3. Wiederholen Sie den Vorgang in Schritt 2.

Bei diesem Verfahren beginnt der Algorithmus mit der am wenigsten gewichteten Kante und wählt bei jedem Zyklus jede Kante aus. Daher muss der Graph im Algorithmus nicht verbunden werden. Kruskal-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 Kruskal-Algorithmus mit einer Kante beginnt.

• Die Algorithmen von Prim erstrecken sich von Knoten zu Knoten, während der Kruskal-Algorithmus die Kanten so auswählt, dass die Position der Kante nicht auf dem letzten Schritt basiert.

• Im prim-Algorithmus muss der Graph ein zusammenhängender Graph sein, während der Kruskal auch für getrennte Graphen funktionieren kann.

• Der Algorithmus von Prim hat eine zeitliche Komplexität von O (V²) und Kruskal's zeitliche Komplexität ist O (logV).