Finding MST von gerichteten Graphen mit Prim-Algorithmus

Question

kann mir plz helfen, wie die MST zu finden, die PRIM-Algorithmus. Markieren Sie die Ränder der MST und schreiben, in dem die Reihenfolge die Knoten auf den MST hinzugefügt werden .. dank

Answer 1

Zitiert The Directed Minimum Spanning Tree Problem:

1. Verwerfen Sie den Bögen, die die Wurzel, wenn eine Eingabe; Wählen Sie für jeden Knoten außer dem Stamm den eintretenden Bogen mit den niedrigsten Kosten ; Lassen Sie die ausgewählten n-1 Bögen die Menge S.
2. Wenn kein Zyklus gebildet wird, ist G (N, S) ein MST. Ansonsten, fahre fort.
3. Für jeden Zyklus gebildet wird, kontrahieren die Knoten in den Zyklus in einen Pseudoknoten (k), und Ändern der Kosten für jeden Bogen die außerhalb eines Knotens (j) in den Kreislauf kommt von einem Knoten (i) der Zyklus gemäß der folgenden Gleichung.
   c (i, k) = c (i, j) - (c (x (j), j) -min_ {j} (c (x (j), j)) hier c (x (j) ., j) sind die Kosten für die Lichtbogen in dem Zyklus, der j tritt
4. Für jeden Pseudoknoten, wählen Sie die eintretenden Lichtbogen, den die kleinst modifizierten Kosten aufweisen, die arc ersetzen, den den gleichen realen Knoten in S eintritt durch den neuen ausgewählten Bogen.
5. zur 2 mit dem kontrahierten graph Schritt.

die zentrale Idee des Algorithmus, um den Austausch zu arc zu finden ist (s), diehatdie minimalen zusätzlichen Kosten zu beseitigen Zyklus (e), wenn vorhanden. Die gegebene Gleichung weist die damit verbundenen Zusatzkosten auf.