Finden Sie die kürzesten Pfade im Komplementdiagramm

7

Ich suche einen Algorithmus, der als Eingabe einen Scheitelpunkt empfängt sund findet die kürzesten Wege von szu allen Eckpunkten im Komplementgraphen (ungerichtet). Der Algorithmus sollte in laufenO(V+E) Zeit, wo E ist die Anzahl der Kanten im Originaldiagramm (nicht das Komplementdiagramm).

Wenn G ist ein Diagramm, das Komplementdiagramm ist wie folgt definiert: eist genau dann eine Kante im Komplementdiagramm, wenn es im Originaldiagramm keine Kante ist. Mit anderen Worten, wir löschen alle vorhandenen Kanten und fügen alle Kanten hinzu, die im Originaldiagramm fehlten.

Also dachte ich natürlich zuerst daran, das Komplementdiagramm zu "erstellen" (die Scheitelpunkte in der Adjazenzliste durch diejenigen zu ersetzen, die dort nicht erscheinen) und dann BFS auf der neuen Liste auszuführen, aber das würde natürlich die Laufzeit bedeuten würde auf den Kanten im Komplementdiagramm basieren, nicht auf dem ursprünglichen.

Ich habe natürlich auch bemerkt, dass nach dem Ausführen von BFS im Originaldiagramm jeder Scheitelpunkt, von dem ein Abstand vorhanden ist sDas ist größer als 1 (im Originaldiagramm) und sollte im Komplementdiagramm zu 1 werden (denn wenn sie im Originaldiagramm keine Nachbarn waren, sind sie im Komplementdiagramm Nachbarn). Aber ich konnte den Algorithmus nicht dazu bringen, nach bestimmten Regeln fortzufahren, wann und auf welche Weise die Entfernung aktualisiert werden sollte. Irgendwelche Vorschläge?

Cauthon
quelle
3
Eine mögliche Richtung besteht darin, zwei Fälle zu betrachten: |E|<c|V|2 und |E|c|V|2für eine Konstante c<1/2. Im zweiten Fall hat der KomplementgraphO(|E|)Kanten, also sind wir fertig. Im ersten Fall ist der Komplementgraph sehr dicht, was dazu beitragen kann, dass der Algorithmus schneller ausgeführt wird.
Yuval Filmus

Antworten:

-1

Ich persönlich verstehe nicht, warum dies als unbeantwortet bleibt .

Das Finden von etwas im Komplementdiagramm und das Finden derselben Sache im Diagramm hat im Wesentlichen dieselbe zeitliche Komplexität (bis zu einem konstanten Faktor).

Da zwischen Kante wechseln (u,v) und nicht kantig (u,v) ist nur O(1)-zeitbetrieb. Wir müssen nichts transformieren oder konvertieren, sondern nur jede Abfrageausgabe negieren .

Thinh D. Nguyen
quelle
1
Es sollte eingefahren werden O(|V|+|E|)Zeit. HinweisEist die Menge der Kanten im Originaldiagramm, nicht im Komplementdiagramm.
xskxzr