Schneller zweitbester MST-Algorithmus?

9

Ich habe damit zu kämpfen.

Wir können MST mit Kruskal-Algorithmus oder Prim-Algorithmus für die MST erhalten.

Und für "zweitbeste" MST kann ich:

  1. Erhalte zuerst MST mit einem der oben genannten Algorithmen.
  2. Für jedes V-1 der optimalen Kante vom MST:
    ein. zuerst entfernen oder markieren Sie die Kante
    b. fahre fort ohne MST zu berechnen Rand
    c. Vergleichen und notieren Sie das "zweitbeste" MST mit vorherige Iteration
  3. Am Ende haben wir "zweitbeste" MST

Aber dies läuft in O (VE), wobei V die Nummer des Eckpunkts und E die Anzahl der Kanten ist.

Wie kann man eine Geschwindigkeit mit Union-find disjoint set oder LCA (niedrigster gemeinsamer Ancester) erreichen?

Hinweise, pseodo Code oder Weblinks Zeiger.

Jede Hilfe wäre sehr willkommen! Danke:)

    
noooooooob 01.03.2014, 03:14
quelle

5 Antworten

3

Ich werde polylogarithmische Lösung für das Problem beschreiben. Lassen Sie uns einige Definitionen vorstellen. Wir bezeichnen:

  1. Menge der Scheitelpunkte des Graphen nach V , Menge der Kanten des Graphen nach E und Menge der MST-Kanten nach T .
  2. Kante des Graphen zwischen den Scheitelpunkten v und u by {v, u} .
  3. Gewicht der Kante e von W(e) und Gewicht der MST von W(T) .

Betrachten wir die Funktion MaxEdge(v, u) , die der Kante mit der größten Gewichtung auf dem einfachen Pfad zwischen v und u entspricht, die zu T gehört. Wenn es mehrere Kanten mit maximalem Gewicht gibt, kann MaxEdge(v, u) gleich einem von ihnen sein.

Um die zweitbeste MST zu finden, müssen wir eine solche Kante finden x = {p, q} , das:

  1. x gehört nicht zu T .
  2. Funktion W(x) - W(MaxEdge(p, q)) ist minimal möglich.

Es ist möglich zu beweisen, dass die zweitbeste MST konstruiert werden kann, indem MaxEdge(p, q) von T entfernt wird und dann x = {p, q} zu T hinzugefügt wird.

Erstellen wir jetzt eine Datenstruktur, die MaxEdge(p, q) in O(log|V|) berechnen kann.

Wählen wir eine Wurzel für den Baum T (es kann ein beliebiger Knoten sein). Wir nennen die Anzahl der Kanten im einfachen Pfad zwischen dem Vertex v und dem Stamm - die Tiefe des Vertex v und bezeichnen sie als Depth(v) . Wir können Depth(v) für alle Knoten in O(|V|) berechnen durch Tiefensuche zuerst .

Lassen Sie uns zwei Funktionen berechnen, die uns helfen, MaxEdge(p, q) zu berechnen:

  1. Parent(v, i) , was gleich dem Eckpunkt ist, der ein Elternteil (möglicherweise nicht direktes Elternteil) von Vertex v mit Tiefe gleich Depth(v) - 2^i .
  2. ist
  3. MaxParentEdge(v, i) , was gleich MaxEdge(v, Parent(v, i)) ist.

Beide können durch eine Wiederholungsfunktion mit Speicherung in O(|V|log|V|) berechnet werden.

%Vor%

Bevor wir MaxEdge(p, q) berechnen können, wollen wir die endgültige Definition vorstellen. Lca(v, u) wird den kleinsten gemeinsamen Vorfahren der Vertices v und u im verwurzelten Baum T bezeichnen. Es gibt viele bekannte Datenstrukturen, die es erlauben, Lca(v, u) query in O(log|V|) oder sogar in O(1) zu berechnen (die Liste der Artikel finden Sie unter Wikipedia ).

Um MaxEdge(p, q) zu berechnen, teilen wir den Pfad zwischen p und q in zwei Teile: von p bis Lca(p, q) , von Lca(p, q) bis q . Jeder dieser Teile sieht wie ein Pfad von einem Eckpunkt zu einigen seiner Eltern aus, daher können wir unsere Funktionen Parent(v, i) und MaxParentEdge(v, i) verwenden, um MaxEdge für diese Teile zu berechnen.

%Vor%

Grundsätzlich bewirkt die Funktion QuickMaxEdge(v, parent_v) Sprünge der Länge 2^i , um den Abstand zwischen parent_v und v zu überbrücken. Während eines Jumps verwendet es vorberechnete Werte von MaxParentEdge(v, i) , um die Antwort zu aktualisieren.

Wenn man bedenkt, dass MaxParentEdge(v, i) und Parent(v, i) vorberechnet ist, arbeitet MaxEdge(p, q) in O(log|V|) , was uns zu einer O(|E|log|V|) Lösung für das anfängliche Problem führt. Wir müssen nur über alle Kanten iterieren, die nicht T gehören, und W(e) - MaxEdge(p, q) für jede von ihnen berechnen.

    
Gerald Agapov 14.10.2015 00:23
quelle
1

Setzen Sie V auf den Scheitelpunkt und E auf den Kantensatz.

Sei T die MST, die mit einem der Standardalgorithmen erhalten wurde.

Sei maxEdgeInPath(u,v) die maximale Kante auf dem eindeutigen Pfad in T von Vertex u zu Vertex v .

Für jeden Knoten u führen Sie BFS für T aus. Dies ergibt maxEdgeInPath (u, x) für alle x , die zu V-u gehören.

Finden Sie eine Kante (x,y) , die nicht zu T gehört, die w(x,y) - w(maxEdgeInPath(x,y))

minimiert

Gewicht von 2ndMST ist W(T) + w(x,y) - maxEdgeInPath(x,y)

Dies basiert auf dem Algorithmus in diesem Link . Ich bin mir nicht sicher, ob das stimmt und ich hoffe, dass jemand hier einen Beweis hinzufügen würde.

Komplexität: Die Berechnung von BST für einen Stützpunkt dauert O(V+E) = O(V) als E = V-1 in T Daher ist die gesamte zeitliche Komplexität O(V^2)

    
arunmoezhi 01.03.2014 23:29
quelle
0
%Vor%     
Prateek 20.03.2014 17:58
quelle
0

Stellen Sie Δ | T | ein = ∞.
Setzen Sie Enew = -1 und Eold = -1.
Für jede Kante, die nicht auf dem Baum ist, mach:
- Fügen Sie dem Baum die Kante hinzu und erstellen Sie einen Zyklus.
- Finde k die maximale Gewichtsgrenze im Zyklus, so dass k! = e.
- entferne k
- Berechne die Änderung des Baumgewichts δ = Gewicht (e) - Gewicht (k).
- wenn δ & lt; Δ | T | dann Δ | T | = δ und Enew = e und Eold = k.
Der neue Baum ist derjenige, der dazu führt, dass Eold durch Enew ersetzt wird.

Die Laufzeit ist proportional zur Anzahl der Kanten von

Quelle:
Ссылка

    
Ajay Karthik 09.07.2014 01:37
quelle
0

Siehe diese Lösung: Ссылка

Hier muss ein weiterer Punkt hinzugefügt werden, nachdem eine Kante hinzugefügt und die maximale gewichtete Kante in dem gebildeten Zyklus berechnet wurde und somit der Unterschied zwischen der neuen und der alten Kante gefunden wird, müssen wir eine Spur der Kante behalten, die ist wodurch der Unterschied minimal ist. Diese bestimmte Kante kann hinzugefügt werden, um einen zweitbesten minimalen Spannbaum zu bilden.

    
Shilpa 13.10.2015 19:42
quelle