Stark zusammenhängende Komponenten mit Kosaraju

Eine stark zusammenhängende Komponente (SCC) eines gerichteten Graphen ist eine maximale Menge von Knoten, sodass es von jedem Knoten zu jedem anderen Knoten innerhalb dieser Menge einen Pfad gibt. Wenn beispielsweise die Knoten A, B und C einen Zyklus bilden (A→B→C→A), gehören sie alle zur selben SCC. Ein einzelner Knoten ohne Selbstschleife bildet seine eigene SCC. SCCs machen die zyklische Struktur eines gerichteten Graphen sichtbar.

Kosarajus Algorithmus findet alle SCCs in O(V + E) mit zwei DFS-Durchläufen. Durchlauf 1: Führen Sie DFS auf dem ursprünglichen Graphen aus und legen Sie die Knoten in der Reihenfolge ihres Abschlusses (Postorder) auf einen Stack. Durchlauf 2: Führen Sie DFS auf dem transponierten (umgekehrten) Graphen aus und verarbeiten Sie die Knoten in umgekehrter Abschlussreihenfolge (indem Sie sie vom Stack nehmen). Jeder DFS-Baum im zweiten Durchlauf entspricht einer SCC.

Im ersten Durchlauf ist die SCC, deren DFS-Baum zuletzt abgeschlossen wird, diejenige ohne ausgehende Kanten zu anderen SCCs (eine „Senken“-SCC im Kondensations-DAG). Im transponierten Graphen hat diese SCC keine eingehenden Kanten von anderen SCCs — daher bleibt eine von ihr ausgehende DFS im zweiten Durchlauf auf diese SCC beschränkt. Jede nachfolgende DFS im zweiten Durchlauf bleibt innerhalb ihrer eigenen SCC, weil alle Kanten zwischen SCCs umgekehrt wurden und nun zu bereits besuchten SCCs führen.

Führen Sie DFS auf dem ursprünglichen Graphen aus und legen Sie jeden Knoten nach seinem Abschluss auf einen Stack (Postorder). In diesem Durchlauf interessieren uns die Komponenten nicht — nur die Abschlussreihenfolge. Der zuletzt abgeschlossene Knoten befindet sich in einer „Quellen“-SCC des Kondensations-DAG.

Nehmen Sie die Knoten aus dem Abschluss-Stack (zuerst die mit der größten Abschlusszeit) und führen Sie DFS auf dem transponierten Graphen aus. Jede DFS von einem unbesuchten Knoten entdeckt genau eine SCC. Markieren Sie alle Knoten, die bei dieser DFS erreicht werden, als zu derselben Komponente gehörig.

Der transponierte Graph kehrt jede Kante um: Wenn der ursprüngliche Graph u → v enthält, enthält die Transposition v → u. Die Transposition bewahrt die SCCs — wenn A und B im ursprünglichen Graphen zur selben SCC gehören, gehören sie auch in der Transposition zur selben SCC (da alle Pfade umgekehrt werden, die Knoten aber weiterhin verbinden). Wenn Sie die Transposition bereits beim Einlesen der Eingaben erstellen (wie oben gezeigt), entfällt ein separater Transpositionsschritt.

Bei großen Graphen ersetzen Sie rekursive DFS durch iterative DFS mit einem expliziten Stack, um Pythons Rekursionslimit zu vermeiden. Die iterative Variante legt Knoten auf den Stack, verarbeitet sie und verwaltet eine separate „return“-Markierung, um die Postorder zu simulieren.

Tarjans Algorithmus findet SCCs in einem einzigen DFS-Durchlauf (im Vergleich zu den zwei Durchläufen von Kosaraju). Dabei verwaltet er einen Stack mit Knoten und weist jedem Knoten eine Entdeckungszeit und einen Low-Link-Wert zu. Wenn die Entdeckungszeit eines Knotens seinem Low-Link-Wert entspricht, ist er die Wurzel einer SCC. Tarjans Algorithmus ist etwas komplexer zu implementieren, vermeidet jedoch das Erstellen des transponierten Graphen. Beide Verfahren haben die Komplexität O(V + E).

SCCs werden verwendet für: (1) Compiler-Optimierung — zum Identifizieren gegenseitig rekursiver Funktionen. (2) Analyse sozialer Netzwerke — zum Finden eng vernetzter Gemeinschaften. (3) 2-SAT-Problem — zum Bestimmen der Erfüllbarkeit von Klauseln mit zwei Literalen. (4) Web-Crawling — zum Identifizieren von Seiten-Clustern mit vielen Querverweisen. (5) Kondensations-DAG — nach dem Finden der SCCs ist die Kondensation des Graphen ein DAG, der eine topologische Analyse zyklischer Graphen ermöglicht.

Die Kondensation eines gerichteten Graphen fasst jede SCC zu einem einzelnen Knoten zusammen und fügt eine Kante zwischen zwei Superknoten hinzu, wenn eine Kante zwischen ihren zugehörigen SCCs existiert. Das Ergebnis ist immer ein DAG — Sie können darauf eine topologische Sortierung ausführen. Dadurch können Algorithmen, die nur auf DAGs funktionieren (wie DP), auf beliebige gerichtete Graphen angewendet werden, indem Sie mit deren Kondensation arbeiten.

Die Anzahl der SCCs in einem gerichteten Graphen gibt Aufschluss über seine zyklische Struktur. Ein DAG hat n SCCs (jeder Knoten ist seine eigene SCC). Ein stark zusammenhängender Graph hat genau 1 SCC. Allgemein bilden die SCCs nach ihrer Zusammenfassung einen DAG — die Kondensation. Wenn der Kondensations-DAG eine eindeutige Quelle (Knoten mit Eingangsgrad 0) und eine eindeutige Senke (Knoten mit Ausgangsgrad 0) besitzt, gelten bestimmte Zusammenhangseigenschaften. Diese Eigenschaften werden in Aufgaben zur Erreichbarkeit nach dem Hinzufügen einer minimalen Anzahl von Kanten geprüft.

In dieser Lektion haben Sie gelernt: SCCs sind maximale Mengen, in denen jeder Knoten von jedem anderen aus erreichbar ist, Kosaraju verwendet zwei DFS-Durchläufe — zunächst auf dem ursprünglichen Graphen zur Bestimmung der Abschlussreihenfolge, danach auf dem transponierten Graphen und die Kondensation jedes gerichteten Graphen ist ein DAG, der für weitere Analysen verwendet werden kann. Als Nächstes erstellen wir TrieNode-Datenstrukturen für Einfüge-, Such- und Präfixoperationen.