Kosaraju SCC Finder

Pseudocode

Zwei Tiefensuchen und ein transponierter Graph. In beiden Durchläufen geschieht nichts Raffiniertes; die ganze Arbeit leistet die Reihenfolge, in der der zweite läuft.

Kosaraju(graph):
    // Durchlauf 1: Abschlussreihenfolge festhalten
    ordnung = []
    für jedes unbesuchte u: dfs1(u)

    dfs1(u): markiere u besucht
             für jede Kante (u,v): wenn unbesucht: dfs1(v)
             ordnung.anhängen(u)        // beim Abschluss

    // Durchlauf 2: DFS auf der Transponierten, umgekehrt
    gt = transponiere(graph)    // jede Kante umdrehen
    für jedes u in umgekehrt(ordnung):
        wenn u unbesucht:
            der in gt von u aus gewachsene Baum ist eine SCC

Warum das funktioniert: Das Umdrehen aller Kanten lässt die starken Zusammenhangskomponenten unberührt, denn wenn du von x nach y und zurück kamst, kannst du das weiterhin. Was die Umkehrung sehr wohl ändert, ist die Richtung der Kanten zwischen den Komponenten. Beim zuletzt abgeschlossenen Knoten zu beginnen garantiert, dass du in einer Quellkomponente der Kondensation startest, sodass die zweite DFS nicht aus ihr heraus in eine andere Komponente entweichen kann.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe Kosaraju auf demselben gerichteten Graphen wie im Tarjan-Beispiel aus, damit sich beide unmittelbar vergleichen lassen.

Beispielgraph: Gerichtete Kanten A nach B, B nach C, C nach A, B nach D, D nach E, E nach D und C nach F.

1. Durchlauf 1 ab A. Steige A, B, C hinab; C nach A ist bereits besucht, also nimm C nach F. F hat keine ausgehenden Kanten und schließt zuerst ab. Danach schließt C ab, die Suche kehrt zu B zurück und nimmt B nach D, dann D nach E; da E nach D bereits besucht ist, schließt E ab, dann D, dann B, dann A.
2. Abschlussreihenfolge. Die Knoten schließen in der Reihenfolge F, C, E, D, B, A ab. Umgekehrt ergibt das die Verarbeitungsreihenfolge für Durchlauf 2: A, B, D, E, C, F.
3. Den Graphen transponieren. Jede Kante dreht sich um: B nach A, C nach B, A nach C, D nach B, E nach D, D nach E, F nach C.
4. Durchlauf 2 beginnt bei A. In der Transponierten erreicht A den Knoten C, C erreicht B, und B erreicht nur A, das bereits besucht ist. Der Baum umfasst A, C und B, die erste Komponente ist also {A, B, C}. Entscheidend ist, dass die Suche nicht nach D oder F entweichen konnte, weil diese Kanten in der Transponierten nach innen und nicht nach außen zeigen.
5. Durchlauf 2 setzt sich fort. Der nächste unbesuchte Knoten in der Reihenfolge ist D. In der Transponierten erreicht D den Knoten B, bereits besucht, und E, das D erreicht, ebenfalls bereits besucht. Die Komponente ist {D, E}. Zuletzt ist F unbesucht: in der Transponierten erreicht es nur C, bereits besucht, es ist also die einelementige Komponente {F}.

Die Komponenten sind {A, B, C}, dann {D, E}, dann {F}. Vergleiche das mit Tarjan auf demselben Graphen, der {F}, dann {D, E}, dann {A, B, C} ausgibt. Beide sind korrekt und beide finden dieselben drei Komponenten, doch Kosaraju gibt sie in vorwärtsgerichteter topologischer Ordnung der Kondensation aus, Tarjan in umgekehrter. Wenn die Reihenfolge für deinen nachgelagerten Code eine Rolle spielt, ist das der Grund, sich für eines der beiden zu entscheiden.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V + E)

Zwei Tiefensuchen kosten je O(V + E), und der Aufbau des transponierten Graphen erfordert einen Durchlauf über alle Kanten, ebenfalls O(V + E). In Summe ergibt das O(V + E). Beim Speicher verliert Kosaraju wirklich gegen Tarjan: er muss die transponierte Adjazenzstruktur vorhalten, also eine zweite vollständige Kopie der Kantenliste mit O(V + E), während Tarjan nur O(V) an Buchführung auf dem Originalgraphen benötigt. Bei einem Graphen mit zig Millionen Kanten ist dieser Unterschied ausschlaggebend, weshalb Tarjan im produktiven Einsatz meist gewinnt, obwohl beide zeitlich asymptotisch identisch sind.

Wann Kosaraju SCC-Algorithmus passt und wann nicht

Alle linearen SCC-Algorithmen kosten O(V + E). Die Unterschiede liegen in Speicher, Anzahl der Durchläufe und der Frage, wie leicht der Code korrekt wird.

Häufige Fehler

• Die Abschlussreihenfolge vorwärts statt rückwärts verwenden. Der zweite Durchlauf muss die Knoten in absteigender Abschlusszeit verarbeiten. Läuft er aufsteigend, startet er in einer Senkenkomponente und die DFS läuft über Komponentengrenzen hinaus, wodurch getrennte SCCs verschmelzen. Das ist der Fehler, der Kosaraju auszeichnet.
• Bei der Entdeckung statt beim Abschluss an die Reihenfolge anhängen. Der Knoten muss angehängt werden, wenn seine Rekursion abgeschlossen ist, nicht wenn er zuerst erreicht wird. Die Entdeckungsreihenfolge trägt keine der Informationen, auf die der Algorithmus angewiesen ist.
• Vergessen, die Besuchtmenge zwischen den Durchläufen zurückzusetzen. Die beiden Suchen sind unabhängig. Nimmt man die Besuchtmarkierungen des ersten Durchlaufs in den zweiten mit, wird nichts mehr erkundet und alle Komponenten kommen leer zurück.
• An Ort und Stelle transponieren. Der zweite Durchlauf braucht den umgekehrten Graphen, während die Abschlussreihenfolge aus dem Original stammt. Die ursprünglichen Adjazenzlisten zu verändern statt eine separate Transponierte aufzubauen beschädigt beides.
• Annehmen, es funktioniere auf ungerichteten Graphen. Starker Zusammenhang ist ein gerichteter Begriff. In einem ungerichteten Graphen ist jede Zusammenhangskomponente trivialerweise stark zusammenhängend, und eine einzige DFS oder Union-Find beantwortet die Frage weit günstiger.

Häufig gestellte Fragen

Wie funktioniert der Algorithmus von Kosaraju?

Er führt eine Tiefensuche auf dem Originalgraphen aus und hält fest, in welcher Reihenfolge die Knoten abschließen. Dann dreht er jede Kante um und führt eine zweite Tiefensuche aus, wobei die Knoten in absteigender Abschlussreihenfolge verarbeitet werden. Jeder im zweiten Durchlauf gewachsene Baum ist genau eine starke Zusammenhangskomponente.

Warum funktioniert das Umdrehen der Kanten?

Das Umdrehen erhält den starken Zusammenhang, denn eine Hin- und Rückreise zwischen zwei Knoten besteht weiterhin, wenn alle Kanten kippen. Was sich ändert, ist die Richtung zwischen den Komponenten. Beim zuletzt abgeschlossenen Knoten zu beginnen setzt dich in eine Quellkomponente der Kondensation, und nach der Umkehrung werden deren ausgehende Verbindungen zu eingehenden, sodass die Suche in der Komponente gefangen bleibt und nicht entweichen kann.

Was ist der Unterschied zwischen Kosaraju und Tarjan?

Beide sind O(V + E). Kosaraju nutzt zwei DFS-Durchläufe plus eine transponierte Kopie des Graphen und braucht daher O(V + E) zusätzlichen Speicher; Tarjan nutzt einen Durchlauf und O(V) zusätzlichen Speicher. Kosaraju ist leichter zu erklären und zu implementieren, Tarjan in der Praxis schneller und sparsamer. Zudem geben sie die Komponenten in entgegengesetzter Reihenfolge aus: Kosaraju in vorwärtsgerichteter topologischer Ordnung der Kondensation, Tarjan in umgekehrter.

Wie ist die Zeitkomplexität des Algorithmus von Kosaraju?

O(V + E) Zeit, aus zwei linearen Durchläufen plus einem linearen Durchlauf zum Aufbau der Transponierten. Der Speicher beträgt O(V + E), weil der transponierte Graph vorgehalten werden muss, was der wesentliche praktische Unterschied zu Tarjan ist.

Kann Kosaraju Komponenten in einem ungerichteten Graphen finden?

Es würde funktionieren, wäre aber sinnlos. In einem ungerichteten Graphen ist jede Zusammenhangskomponente bereits stark zusammenhängend, sodass eine einzige DFS oder eine Union-Find-Struktur sie in einem Durchlauf findet, ohne eine Transponierte aufzubauen.