Unterschied zwischen Kruskal und Prim
Kruskal gegen Prim
In der Informatik sind die Algorithmen von Prim und Kruskal ein gieriger Algorithmus, der einen minimalen Spannungsbaum für eine angeschlossene gewichtete, ungerichtete Grafik findet. Ein Spanning -Baum ist ein Untergraphen eines Graphen, so dass jeder Knoten des Diagramms durch einen Pfad verbunden ist, der ein Baum ist. Jeder Spannungsbaum hat ein Gewicht und die minimal möglichen Gewichte/Kosten aller Spannbäume sind der minimale Spanning -Baum (MST).
Mehr über Prims Algorithmus
Der Algorithmus wurde 1930 von tschechischem Mathematiker Vojtěch Jarník entwickelt und später unabhängig vom Informatiker Robert C. Prim im Jahr 1957. Es wurde 1959 von Edsger Dijkstra wiederentdeckt. Der Algorithmus kann in drei wichtigen Schritten 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 ist)
2. Betrachten Sie die Gewichte jeder mit den Knoten im Baum verbundenen Kante 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 der Grafik. (Wählen Sie eine eine, wenn zwei oder mehr Minimum existieren)
3. Wiederholen Sie Schritt 2, bis N-1-Kanten zum Baum hinzugefügt werden.
Bei dieser Methode beginnt der Baum mit einem einzelnen willkürlichen Knoten und erweitert sich von diesem Knoten mit jedem Zyklus von vorne. Damit der Algorithmus ordnungsgemäß funktioniert, muss der Diagramm eine angeschlossene Grafik sein. Die Grundform des Algorithmus des Prims hat eine zeitliche Komplexität von O (V)2).
Mehr über den Algorithmus von Kruskal
Der von Joseph Kruskal entwickelte Algorithmus erschien 1956 im Verfahren der American Mathematical Society. Der Algorithmus von Kruskal kann auch in drei einfachen Schritten ausgedrückt werden.
Angesichts der Grafik mit n Knoten und dem jeweiligen Gewicht jeder Kante,
1. Wählen Sie den Bogen mit dem geringsten Gewicht des gesamten Graphen aus, fügen Sie dem Baum hinzu und löschen Sie aus der Grafik.
2. Wählen Sie der verbleibenden Wählen Sie die am wenigsten gewichtete Kante auf eine Weise, die keinen Zyklus bildet. Fügen Sie die Kante zum Baum hinzu und löschen Sie aus dem Diagramm. (Wählen Sie eine eine, wenn zwei oder mehr Minimum existieren)
3. Wiederholen Sie den Vorgang in Schritt 2.
Bei dieser Methode beginnt der Algorithmus mit der am wenigsten gewichteten Kante und wählt die gesamte Kante in jedem Zyklus fort. Daher muss im Algorithmus das Diagramm nicht angeschlossen werden. Der Algorithmus von Kruskal hat eine zeitliche Komplexität von O (logv)
Was ist der Unterschied zwischen dem Algorithmus von Kruskal und Prim?
• Der Prim -Algorithmus initialisiert mit einem Knoten, während der Algorithmus von Kruskal mit einer Kante initiiert.
• 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 ein Diagramm ein verbundenes Diagramm sein, während die Kruskal auch auf getrennten Diagramme funktionieren kann.
• Der Algorithmus von Prim hat eine zeitliche Komplexität von O (V)2) und Kruskals Zeitkomplexität ist o (logv).
