Zweiter min Kostenspannender Baum

Question

Zweiter min Kostenspannender Baum

9

Ich schreibe einen Algorithmus, um den zweiten min-Kosten-Spannbaum zu finden. Meine Idee war wie folgt:

Benutze kruskals, um die niedrigste MST zu finden.
Löschen Sie die niedrigste Kostenkante der MST.
Führe kruskals erneut auf dem gesamten Graphen aus.
gib die neue MST zurück.

Meine Frage ist: Wird das funktionieren? Gibt es vielleicht einen besseren Weg, dies zu tun?

algorithm graph

Evil 22.04.2010, 16:30

quelle

7 Antworten

Tags und Links algorithm graph

Django: Verwenden von Annotate, Count und Distinct in einem Queryset getJSON Callback wird nicht ausgelöst

score 9 · Answer 1

Du kannst es in O machen (V ²). Berechnen Sie zuerst die MST mit dem Prim-Algorithmus (kann in O gemacht werden (V ²) ).

Berechne max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST . Kann in O gemacht werden (V ²).

Finde eine Kante (u, v) , die NICHT Teil der MST ist, die abs(max[u, v] - weight(u, v)) minimiert. Kann in O (E) == O (V 2 ) gemacht werden.

Gib MST' = MST - {the edge that has max[u, v] weight} + {(u, v)} zurück, was dir die zweitbeste MST geben wird.

Hier ist ein Link zu Pseudocode und detaillierteren Erklärungen.

score 8 · Answer 2

Betrachten Sie diesen Fall:

%Vor%

Die MST besteht aus A-B-D-C (Kosten 6). Die zweite minimale Kosten ist A-B-C-D (Kosten 7). Wenn Sie die Kante mit den niedrigsten Kosten löschen, erhalten Sie stattdessen A-C-B-D (Kosten 105).

Also wird Ihre Idee nicht funktionieren. Ich habe jedoch keine bessere Idee ...

score 4 · Answer 3

Sie können dies tun - versuchen Sie, die Kanten der MST einzeln aus der Grafik zu entfernen und führen Sie die MST aus, wobei Sie die Min aus der MST nehmen. Das ist ähnlich wie bei Ihnen, außer iterativ:

Benutze Krusbels, um MST zu finden.
Für jede Kante in MST:
1. Entfernen Sie die Kante aus dem Diagramm
2. Berechne MST 'auf MST
3. Verfolgen Sie die kleinste MST
4. Kante zum Diagramm hinzufügen
Gib die kleinste MST zurück.

score 3 · Answer 4

Das ist Larrys Antwort ähnlich.

Nachdem MST gefunden wurde,

Für jedes new_edge = keine Kante in MST

Fügen Sie new_edge zu MST hinzu.
Finde den Zyklus, der gebildet wurde.
Finde die Kante mit dem maximalen Gewicht in Zyklus, der nicht die Nicht-MST-Kante ist du hast hinzugefügt.
Zeichnen Sie die Gewichtszunahme als W_Inc auf = w (new_edge) - w (max_weight_edge_in_cycle).
Wenn W_Inc & lt; Min_W_Inc_Seen_So_Far Dann
- Min_W_Inc_Seen_So_Far = W_Inc
- edge_to_add = new_edge
- edge_to_remove = max_weight_edge_in_cycle

Lösung von folgendem Link.
Ссылка

score 2 · Answer 5

2

leicht editieren zu Ihrem Algo.

%Vor%

aitrom 20.11.2013 22:31

quelle

score 1 · Answer 6

Hier ist ein Algorithmus, der den 2. minimalen aufspannenden Baum in O (n ^ 2)

berechnet

Finden Sie zuerst den minimalen Spannbaum (T) heraus. Es dauert O (n ^ 2) ohne Verwendung von Heap.
Wiederholen Sie für jede Kante e in T. = O (n ^ 2)
Sagen wir, die aktuelle Baumkante ist e. Dieser Baumrand teilt den Baum in zwei Bäume, sagen wir T1 und T-T1. e=(u,v) , wobei u in T1 und v in T-T1 ist. = O (n ^ 2)

Wiederholen Sie dies für jeden Knoten v in T-T1. = O (n ^ 2)

Wählen Sie Kante e'=(u,v) für alle v in T-T1 und e 'ist in G (Originalgraph) und es ist minimal
Berechne das Gewicht des neu gebildeten Baumes. Sagen wir W=weight(T)-weight(e)+weight(e')
Wählen Sie die T1, die ein Mindestgewicht hat

score 0 · Answer 7

0

Ihr Ansatz wird nicht funktionieren, da es der Fall sein könnte, dass min. Gewicht Kante in der MST ist eine Brücke (nur eine Kante verbindet 2 Teile des Graphen), so dass diese Kante aus dem Satz zu 2 neue MST im Vergleich zu einem MST zu löschen.

mridul 07.10.2013 04:58

quelle