Angenommen, die Kanten sind ungerichtet, haben ein eindeutiges Gewicht und keine negativen Pfade. Erzeugen diese Algorithmen die gleichen minimalen Spannbäume?
graphs
trees
minimum-spanning-tree
Death_by_Ch0colate
quelle
quelle
Antworten:
Gefunden dies die besagt , dass , wenn alle Bedingungen , die ich oben erwähnt erfüllt sind, eine grafische Darstellung notwendigerweise eine einzigartige MST hat. In Bezug auf meine Frage führen die Algorithmen von Kruskal und Prim daher notwendigerweise zum gleichen Ergebnis.
quelle
Wenn der MST eindeutig ist, wird er zwangsläufig von allen Algorithmen erzeugt.
Wenn der MST nicht eindeutig ist, können sich die Ausgaben aufgrund unterschiedlicher Knotenverarbeitungsreihenfolgen unterscheiden (sogar zwei unterschiedliche Implementierungen desselben Algorithmus können dies), aber die Gesamtgewichte sind identisch. In diesem Fall ist der MST eine Fehlbezeichnung.
quelle
Um die Antwort von Yves Daoust zu ergänzen , das folgende Diagramm
In diesem Diagramm haben wir 3 Knoten und 3 Kanten, die jeweils das gleiche Gewicht haben. Offensichtlich bilden 2 beliebige Kanten eine MST für dieses Diagramm. Welche zwei Kanten ausgewählt werden, hängt jedoch nicht nur vom Algorithmus ab, sondern auch von der Implementierung des Algorithmus. Wenn ich beispielsweise die Knoten in einer Liste speichere, kann ich sie in einer anderen Reihenfolge besuchen als wenn ich die Knoten in einer Menge gespeichert habe, selbst wenn ich ab diesem Zeitpunkt denselben MST-Algorithmus verwende.
Wenn meine Implementierung auf Zeigerarithmetik basiert (was einige Container in einigen Sprachen tun), kann ich sogar jedes Mal, wenn ich den Algorithmus ausführe, einen anderen MST auswählen!
quelle
set
oderdict
in Python 3.3+: Hashes werden mit einem Wert gesalzen, der für jeden Lauf unterschiedlich ist, um Denial-of-Service-Angriffe zu erschweren.