graph - Die Umsetzung der Aktualisierung der Minimum-Spanning-Tree nach dem hinzufügen einer neuen Kante

Hier ist eine Verbrauchsteuer

Nehmen wir an, wir sind angesichts der minimalen spannenden Baum T von einem gegebenen Graphen G
(mit n Ecken und m Kanten) und eine neue Kante e = (u, v) mit Gewicht w
wir werden hinzufügen. B. Geben Sie einen effizienten Algorithmus zu finden, die minimale
spanning tree des Graphen G + e. Ihr Algorithmus ausgeführt werden soll in O(n)
Zeit bekommen Sie den vollen Kredit.

Habe ich diese Idee:

In the MST, just find out the path between u and v. Then find the edge (along the path) with maximum weight; if the maximum weight is bigger than w, then remove that edge from the MST and add the new edge to the MST.

Der schwierige Teil ist, wie dies in O(n) Zeit und ist es auch ich stecken.

Die Frage ist, dass, wie die MST gespeichert ist. Im normalen Prim ' s Algorithmus MST gespeichert ist, als einen übergeordneten array, d.h., jedes element ist das übergeordnete Element des nach vertex.

Also nehmen wir an, die Verbrauchsteuern, geben Sie mir einen übergeordneten array, der angibt, der MST, wie kann ich die Veröffentlichung des obigen Algorithmus in O(n)?

Ersten, wie kann ich identifizieren, den Pfad zwischen u und v von der übergeordneten array? Ich kann zwei Vorgänger-arrays für u und v, dann schauen Sie auf die gemeinsamen Vorfahren, dann bekomme ich die Weg, obwohl in umgekehrter. Ich glaube, für dieses Teil zu finden, den gemeinsamen Vorfahren, zumindest habe ich es in O(n^2), richtig?

Dann haben wir das Weg. Aber wir müssen noch finden, das Gewicht jeder Kante auf dem Pfad. Da ich vermute, dass der graph verwenden Nachbarschaft-Liste für Prim ' s Algorithmus, haben wir O(m) (m ist die Anzahl der Kanten), um jedes Gewicht von der Kante.

...

So, ich sehe es nicht möglich ist, den Algorithmus in O(n). Bin ich falsch?

InformationsquelleAutor Jackson Tale | 2012-05-01

  1. 1

    Die Idee, die Sie haben, ist richtig. Beachten Sie, dass die Suche nach dem Weg zwischen u und v ist O(n). Ich nehme an, Sie haben eine parent array Ermittlung der MST. tracking der Weg (für max edge) von u zu v oder u zu root vertex sollte nur O(n). Wenn Sie erreichen root vertex, nur verfolgen Sie den Weg von v zu u oder root vertex.

    Jetzt haben Sie den Pfad aus u -> u1 ... -> max_path_vert1 -> max_path_vert2 -> ... -> v, entfernen Sie das edge - max_path_vert1->max_path_vert2 (vorausgesetzt, diese ist größer als die zusätzlichen Rand) und Umgekehrt die Eltern für u->...->max_path_vert1 und mark parent[u] = v.

    Edit: Weitere Erläuterung für Klarheit

    Beachten Sie, dass die MST-es wird genau ein Pfad zwischen jedem paar von Ecken. Also, wenn Sie verfolgen kann, von u->y und v->y haben Sie nur verfolgt durch atmost n Eckpunkte. Wenn Sie verfolgt mehr als n Eckpunkte das bedeutet, dass Sie besucht einen Eckpunkt zweimal, das wird nicht passieren, in ein MST. Ok, nun hoffentlich bist du davon überzeugt, dass es O(n) zu verfolgen, von u->y und v->y. Sobald Sie diese Wege, die Sie gegründet haben, einen Weg aus u->v. Sehen Sie, wie? Ich gehe davon aus das ist ein ungerichteter graph, da die Suche nach MST bei gerichteten Graphen ist ein anderes Konzept an sich. Für ungerichtete Graphen, wenn man einen Pfad von x->y Sie haben einen Pfad von y-x. Also u->y->v vorhanden. Sie nicht sogar brauchen, um eine Rückverfolgung von y->v, da die GEWICHTE für v->y wird derselbe sein wie der y->v. Suchen Sie sich einfach die Kante mit dem maximalen Gewicht, wenn Sie die Ablaufverfolgung von u->y und v->y.

    Nun für die Suche nach kantengewichten in O(1); wie speichern Sie Ihre aktuellen GEWICHTE? Nähe Liste oder Nachbarschaft-matrix? Für O(1) Zugriff, speichern Sie es so, wie Eltern vertex-array gespeichert. Also weight[v] = weight(v, parent[v]). Damit hat man O(1) zugreifen. Hoffe, das hilft.

    Wenn ich parent-array für die MST, ich glaube nicht, dass die Verfolgung der Pfad zwischen u und v ist O(n). Zum Beispiel, wenn u nicht v ist Vorfahr, und v ist nicht u die Vorgänger, stattdessen werden u und v hat einen gemeinsamen Vorfahren y Sie können Spur von u nach y und von v nach y, wie kommt es, dass man zurückverfolgen kann von u nach v oder von v nach u in O(n)?
    Und auch aus der übergeordneten array, wie kann man das Gewicht jeder Kante in O(1)?
    Bearbeitet meine Antwort für mehr details, Ihre Fragen beantworten. Hoffe, dass klärt.

    InformationsquelleAutor deebee

  2. 0

    Gut deine Lösung richtig ist.

    Aber was die Durchführung angeht, ich sehe nicht ein, warum Sie mit G anstelle von T zu finden, den Pfad zwischen u und v. Mit einer Suche traversal in T für den Pfad zwischen u und v ist, erhält man O(n). - Das heißt, man kann davon ausgehen, dass v die Wurzel und führt eine Depth-First-Search-Algorithmus [in diesem Fall müssen Sie davon ausgehen, alle Nachbarn von v, die als Kinder] - und stoppen Sie die DFS-sobald Sie finden u - dann, der Knoten in dem stack entspricht dem Pfad zwischen u und v.

    Ist es einfach danach zu finden, die Kosten für jede Kante in dem Pfad (O(n)), und es ist ebenso leicht zu löschen/hinzufügen von Kanten. In insgesamt O(n).

    Hilft das irgendwie ?

    Oder vielleicht sind Sie immer O(n^2) - nach meinem Verständnis - weil Sie auf die Kinder eines Knotens v in T in O(n) - Hier haben Sie Ihre Datenstruktur als ein array zugeordnet, so dass die Kosten reduziert sich auf O(1). [für instace, {a,b,c,u,w}(vertices) -> {0,1,2,3,4}(Indizes der Eckpunkte).

    Ich denke, der Suche nach dem Pfad zwischen u und v kostet mehr Zeit, wenn die MST wird als parent-array.
    Ich weiß wirklich nicht, was du meinst, die von übergeordneten array ehrlich, aber in den algorithmen, wenn Sie nicht über eine geeignete Datenstruktur dann nicht erwarten, dass eine gute Leistung immer.
    Würden Sie bitte erklären, wie Ihr Baum gespeichert ist (in den details) - kann ich fnid die genaue Art und Weise, es zu tun, wenn möglich

    InformationsquelleAutor AJed

Schreibe einen Kommentar