Tarjan SCC Finder

Pseudocode

Eine DFS, ein Stapel, zwei Zahlen je Knoten. Die Kernidee: jede starke Zusammenhangskomponente hat eine eindeutige Wurzel, nämlich den zuerst entdeckten Knoten in ihr.

strongconnect(u):
    entd[u] = low[u] = ++zeit
    stapel.push(u); aufStapel[u] = wahr

    für jede Kante (u, v):
        wenn v unbesucht:
            strongconnect(v)
            low[u] = min(low[u], low[v])
        sonst wenn aufStapel[v]:
            low[u] = min(low[u], entd[v])
        // sonst: v liegt in einer fertigen SCC, ignorieren

    wenn low[u] == entd[u]:        // u ist SCC-Wurzel
        Stapel bis einschließlich u abräumen
        die abgeräumte Menge ist eine SCC

Die aufStapel-Prüfung trennt Tarjan von einem naiven Low-Link-Schema. Eine Kante zu einem besuchten Knoten, der bereits einer abgeschlossenen Komponente zugeordnet ist, sagt nichts über die eigene Komponente aus und muss übersprungen werden; sie einzubeziehen würde zwei tatsächlich getrennte SCCs verschmelzen. Beachte auch die Asymmetrie: eine Baumkante bezieht low[v] ein, eine Rückkante bezieht entd[v] ein, und beides zu verwechseln ist der andere klassische Fehler.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe Tarjan auf einem gerichteten Graphen aus, der einen Dreierzyklus, einen Zweierzyklus und einen Knoten enthält, der zu keinem von beiden gehört.

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. Abstieg A, B, C. entd und low starten gleich: A erhält 1, B erhält 2, C erhält 3. Alle drei liegen auf dem Stapel.
2. C nach A ist eine Rückkante. A ist besucht und liegt noch auf dem Stapel, also low[C] = min(3, entd[A] = 1) = 1. Beachte, dass hier entd[A] verwendet wird, nicht low[A].
3. C nach F, und F wird allein abgeräumt. F erhält entd 4 und hat keine ausgehenden Kanten, low[F] bleibt also 4. Da low[F] gleich entd[F] ist, ist F eine SCC-Wurzel und wird als Komponente {F} allein abgeräumt. Ein Knoten auf keinem Zyklus bildet stets seine eigene einelementige SCC.
4. B nach D nach E, und E schließt zurück. D erhält entd 5, E erhält entd 6. Die Kante E nach D findet D auf dem Stapel, also low[E] = min(6, entd[D] = 5) = 5. E ist keine Wurzel, da low[E] von 5 nicht gleich entd[E] von 6 ist, es wird also noch nichts abgeräumt.
5. D ist eine Wurzel. Zurück bei D gilt low[D] = min(5, low[E] = 5) = 5, was entd[D] entspricht. D ist eine SCC-Wurzel, der Stapel gibt also E und danach D frei und liefert die Komponente {D, E}.
6. A ist eine Wurzel. Beim Abwickeln gilt low[B] = min(2, low[C] = 1, low[D] = 5) = 1 und low[A] = min(1, low[B] = 1) = 1, was entd[A] entspricht. Der Stapel gibt C, B und A frei und liefert {A, B, C}.

Die endgültigen Low-Link-Werte sind A 1, B 1, C 1, F 4, D 5, E 5, und die Komponenten erscheinen in der Reihenfolge {F}, dann {D, E}, dann {A, B, C}. Zwei Dinge sind bemerkenswert. Die Komponenten werden in umgekehrter topologischer Ordnung der Kondensation ausgegeben, weshalb Tarjan der übliche erste Schritt für 2-SAT ist. Und F, vom Zyklus aus erreichbar, aber ohne Rückweg, bildet korrekt seine eigene Komponente, statt in {A, B, C} aufzugehen.

Komplexität und woher sie kommt

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

Eine einzige Tiefensuche besucht jeden Knoten einmal und betrachtet jede gerichtete Kante genau einmal, was O(V + E) ergibt. Jeder Knoten wird genau einmal auf den Stapel gelegt und einmal entnommen, die Stapeloperationen summieren sich also über den gesamten Lauf zu O(V). Der zusätzliche Zustand besteht aus Entdeckungszeit, Low-Link und Stapelmarkierung je Knoten sowie dem Rekursionsstapel, alles O(V). Tarjan schafft das in einem Durchlauf, während Kosaraju zwei vollständige Durchläufe plus den Aufbau des transponierten Graphen benötigt, weshalb Tarjan in der Praxis meist bevorzugt wird, obwohl beide linear sind.

Wann Tarjan SCC-Algorithmus passt und wann nicht

Alle drei linearen SCC-Algorithmen haben dieselben asymptotischen Kosten, die Wahl geht also um Konstanten, Speicher und die Frage, wie leicht der Code korrekt wird.

Häufige Fehler

• Bei einer Rückkante low[v] statt entd[v] verwenden. Bei einer Baumkante beziehst du low[v] ein, bei einer Rückkante zu einem Knoten auf dem Stapel entd[v]. Für Rückkanten low[v] zu verwenden kann einen Wert aus einer anderen Komponente einschleppen und SCCs verschmelzen, die getrennt bleiben müssten. Die beiden Fälle sind wirklich verschieden.
• Die aufStapel-Prüfung weglassen. Eine Kante zu einem besuchten Knoten, der bereits in eine fertige SCC abgeräumt wurde, muss vollständig ignoriert werden. Ohne diese Prüfung sickern Low-Link-Werte über Komponentengrenzen und die Ausgabe ist auf jedem Graphen mit Querkanten falsch.
• Vergessen, aufStapel beim Abräumen zurückzusetzen. Jeder in eine Komponente abgeräumte Knoten muss seine Markierung verlieren. Bleibt sie gesetzt, greifen spätere Rückkantenprüfungen gegen Knoten, die gar nicht mehr auf dem Stapel liegen, und beschädigen stillschweigend die folgenden Komponenten.
• Auf sehr großen Graphen rekursieren. Tarjan ist von Natur aus rekursiv und die Tiefe entspricht dem längsten Weg. Bei Graphen mit Hunderttausenden aneinandergereihten Knoten läuft der Aufrufstapel über und eine Umschreibung mit explizitem Stapel wird nötig. Das ist kniffliger als bei einer einfachen DFS, weil die Low-Link-Aktualisierung nach der Rückkehr jedes Kindes erfolgen muss.
• Eine Komponentenreihenfolge annehmen, die es nicht gibt. Tarjan gibt die Komponenten in umgekehrter topologischer Ordnung der Kondensation aus, nicht in einer Reihenfolge, die mit den Knotenbezeichnungen zu tun hätte. Brauchst du die vorwärtsgerichtete topologische Ordnung, kehre die Ausgabe um.

Häufig gestellte Fragen

Was ist eine starke Zusammenhangskomponente?

Eine starke Zusammenhangskomponente eines gerichteten Graphen ist eine maximale Knotenmenge, in der jeder Knoten jeden anderen über gerichtete Kanten erreichen kann. Maximal ist wesentlich: du kannst keinen weiteren Knoten hinzufügen und die Eigenschaft behalten. Ein Knoten auf keinem gerichteten Zyklus bildet für sich allein eine Komponente.

Wie funktioniert der Algorithmus von Tarjan?

Er führt eine einzige Tiefensuche aus und weist jedem Knoten einen Entdeckungsindex und einen Low-Link-Wert zu, den kleinsten aus seinem Teilbaum über höchstens eine Rückkante zu einem noch auf dem Stapel liegenden Knoten erreichbaren Index. Knoten werden beim Besuch auf einen Stapel gelegt. Schließt ein Knoten mit einem Low-Link gleich seinem eigenen Index ab, ist er Wurzel einer Komponente, und alles über ihm auf dem Stapel wird als diese Komponente abgeräumt.

Was ist der Unterschied zwischen Tarjan und Kosaraju?

Beide finden starke Zusammenhangskomponenten in O(V + E). Tarjan nutzt eine einzige DFS mit Low-Link-Buchführung und einem Stapel. Kosaraju nutzt zwei DFS-Durchläufe, einen auf dem Originalgraphen für die Abschlusszeiten und einen auf dem transponierten Graphen in absteigender Abschlussreihenfolge. Kosaraju lässt sich leichter erklären; Tarjan ist in der Praxis schneller, da er keine Transponierte aufbaut und nur einmal durchläuft.

Wie ist die Zeitkomplexität von Tarjan SCC?

O(V + E) Zeit und O(V) Speicher. Jeder Knoten wird einmal besucht, jede Kante einmal betrachtet, und jeder Knoten genau einmal auf den Stapel gelegt und wieder entnommen. Das ist optimal, da jeder Algorithmus den gesamten Graphen lesen muss.

Wofür werden starke Zusammenhangskomponenten verwendet?

Zum Verdichten eines gerichteten Graphen zu einem DAG, dem ersten Schritt beim Lösen von 2-SAT. Außerdem für Aufrufgraphanalyse und Entfernung toten Codes in Compilern, Deadlock-Erkennung, das Auffinden gegenseitiger Abhängigkeiten in Paketmanagern und Tabellenkalkulationen sowie Gemeinschaftsstrukturen in gerichteten sozialen Netzwerken.