Überprüfen Sie, ob das Hinzufügen einer Kante zu einer DAG zu einem Zyklus führt

Am Anfang: Es ist ein Programmierwettbewerbsproblem, aber kein laufendes. Leider kann ich keinen Link zu dieser Aufgabe bereitstellen, da sie nicht öffentlich verfügbar ist. Es war von einem der polnischen lokalen Programmierwettbewerbe im Jahr 2011, die von der Warschauer Schule für Informatik organisiert wurden.

Ich habe ein Diagramm mit Eckpunkten ohne Kanten und eine Liste von gerichteten Kanten. In der ten Sekunde wird die te Kante zu einem Diagramm hinzugefügt. Ich möchte wissen, nach welcher Sekunde ein Zyklus in einem Diagramm angezeigt wird.$V$ $(1 \le V \le 5 \cdot 10^5)$$E$ $(1 \le E \le 5 \cdot 10^5)$$i$$i$

Die naheliegendste Lösung wäre, nach dem Hinzufügen jeder Kante eine DFS durchzuführen, aber es würde Zeit dauern . Eine andere Lösung wäre, das Diagramm topologisch sortiert zu halten, und wenn ich eine Kante hinzufüge, könnte ich es so platzieren, dass es die topologische Reihenfolge nicht stört. Dies würde höchstens Zeit dauern . Ich habe bei Google recherchiert und es scheint, dass dies der schnellste Online-Algorithmus ist.$O((V + E)^2)$$O(V^2)$

Da ich alle Kanten vorher kenne, kann ich den Offline-Algorithmus verwenden. Der schnellste Offline-Algorithmus, den ich mir vorstellen kann, ist die binäre Suche. Wenn der Graph nach der ten Sekunde einen Zyklus enthält, hat er offensichtlich einen Zyklus bei jeder anderen Sekunde . Ich kann also eine binäre Suche durchführen, um das kleinste zu finden, indem ich DFS -Zeiten durchführe, wobei jede von ihnen -Zeit benötigt, sodass die Gesamtkomplexität dieser Lösung .$k$$l \ge k$$k$$O(\log E)$$O(V + E)$$O((V + E) \log E)$

Es ist ziemlich schnell, aber ich frage mich, ob es einen schnelleren Offline-Algorithmus gibt. Eine Sache, die ich mir vorstellen kann, ist, für jedes Kantengewicht den Zeitpunkt anzugeben, zu dem diese Kante einem Diagramm hinzugefügt wurde. Dann wäre die Aufgabe gleichbedeutend mit dem Finden eines Zyklus mit minimalem maximalem Kantengewicht. Ich weiß nicht, ob es irgendwohin führt.

KWillets 'Algorithmus

KWillets scheint den besten Algorithmus zu haben . Grundsätzlich wechseln Sie iterativ zwischen den folgenden beiden Schritten:

1. Entfernen Sie für jede Quelle (Scheitelpunkt ohne ausgehende Kante) die Quelle und alle Kanten, die aus ihr herausführen. Wiederholen, bis keine Quellen mehr vorhanden sind.

2. Entfernen Sie die Kante mit der höchsten Nummer, dh die späteste (von allen verbleibenden Kanten). Gehen Sie zurück zu Schritt 1.

Wenn das Diagramm leer ist, machen Sie den letzten Schritt 1 und Schritt 2 rückgängig, und es gibt das früheste Diagramm mit einem Zyklus. Mit anderen Worten, nehmen Sie die letzte im letzten Schritt 2 entfernte Kante, bevor das Diagramm leer wird, und das Diagramm, das diese Kante und alle früheren Kanten enthält, ist die erste, die einen Zyklus enthält.

Da Ihre Kantenliste bereits nach zunehmender Zeit sortiert ist, kann dies in -Zeit implementiert werden. Sie pflegen die Liste der Kanten in einer doppelt verknüpften Liste mit Zeigern zwischen diesen Knoten und der entsprechenden Kante im Diagramm. In Schritt 1 muss Zeit pro Knoten oder Kante gelöscht werden. Wenn Sie einen separaten Arbeitsvorrat aller Quellscheitelpunkte führen und jedes Mal, wenn Sie eine Kante löschen, prüfen Sie, ob dadurch ein neuer Quellscheitelpunkt erstellt wurde.$O(V+E)$$O(1)$

Binäre Suche

Es ist möglich, einige kleine Optimierungen an Ihrer binären Suchmethode vorzunehmen, die jedoch die asymptotische Laufzeit nicht verbessern: Die asymptotische Laufzeit beträgt weiterhin .$O((V+E)\log E)$

Angenommen, Sie analysieren den Graphen zum Zeitpunkt und stellen fest, dass er einen Zyklus enthält. Zerlegen Sie das Diagramm in stark verbundene Komponenten. Jetzt können Sie alle isolierten Knoten dauerhaft löschen (dh Knoten, die sich in einem SCC der Größe 1 befinden). Sie können nicht Teil eines Zyklus sein. Von hier aus können Sie die binäre Suche fortsetzen.$k$

Wenn Sie sich für jede stark verbundene Komponente in stark verbundene Komponenten zerlegen, gehen Sie wie folgt vor. Zählen Sie die Anzahl der Knoten im SCC, z. B. . Sortieren Sie die Kanten innerhalb des SCC in zunehmender Zeit. Schauen Sie sich die Zeit des an, sagen Sie die Zeit . Das erste Mal, wenn sich innerhalb dieser stark verbundenen Komponente ein Zyklus befindet, muss die Zeit oder höher sein. Tun Sie dies für jede stark verbundene Komponente und nehmen Sie die früheste dieser Zeiten. Als Optimierung muss dann keine Zeit früher als bei der binären Suche berücksichtigt werden.$n_0$$n_0$$j_0$$j_0$

Diese beiden Optimierungen bieten jedoch wahrscheinlich bestenfalls nicht mehr als eine kleine Beschleunigung mit konstantem Faktor.

Kahns Algorithmus ist für die topologische Sortierung bekannt, kann aber auch verwendet werden, um stark verbundene Komponenten zu finden. Ich benutze es für die Zyklusprüfung, bei der eine tatsächliche topologische Sortierung nicht benötigt wird. In dieser Variante werden Knoten beim Besuch verworfen, anstatt zur Ausgabe hinzugefügt zu werden, und die Fehlerbeendigung zeigt mindestens einen Zyklus an.

Dabei werden Wurzel- oder Blattknoten (mit einem Grad von 0 bzw. 0) nacheinander aus dem Diagramm entfernt, bis keine Knoten dieses Typs mehr gefunden werden können. Da dieser Prozess einen Zyklus nicht schneiden kann (alle Knoten in einem Zyklus haben einen Grad und einen Grad> 0), wird er mit einem nicht leeren Diagramm beendet, wenn mindestens ein Zyklus vorhanden ist.

Wenn wir die maximal verbleibende Kante e an jedem solchen Endpunkt schneiden, können wir den Prozess fortsetzen, um zu sehen, ob E \ e noch einen Zyklus enthält, und so weiter iterativ, bis wir genug Kanten geschnitten haben, um E azyklisch zu machen. Der letzte derartige Kantenschnitt k ist der erste k, der E [1 ... k] zyklisch macht.

Kahns Algorithmus führt diesen Blattschneidevorgang linear durch, indem er eine Arbeitswarteschlange von zu löschenden Knoten verwendet. Es wird mit den Blättern des gesamten Diagramms initialisiert (von denen mindestens eines vorhanden sein muss, wenn es azyklisch ist), und beim Löschen werden die übergeordneten Knoten überprüft, um festzustellen, ob sie wiederum Blätter werden, und wenn ja Sie werden der Arbeitswarteschlange hinzugefügt. Durch Überprüfen der Nachbarschaft jedes Löschvorgangs wird linear durch das Diagramm gearbeitet, ohne dass Strukturen über die FIFO-Warteschlange hinaus indiziert werden müssen.

Wir können dieselbe Nachbarblattprüfung durchführen, wie wir die maximale Kante schneiden, und alle erstellten Blätter zur Arbeitswarteschlange hinzufügen oder, falls keine erstellt werden, mit dem Schneiden fortfahren.

Um den Maximalschnittprozess linear zu gestalten, müssen wir die maximale nicht gelöschte Kante über einen absteigenden Scan des Kantenarrays ermitteln. Jeder Scan beginnt jedoch dort, wo der vorherige aufgehört hat, und der Algorithmus führt nur einen einzigen Durchlauf durch ganzes Array, so dass dieser Teil insgesamt O (E) ist. Insgesamt glaube ich, dass diese Methode O (V + E) ist, genau wie die von Kahn allein.