Berechnung Starker Zusammenhangskomponenten (SCC-Algorithmus)

Die Berechnung der starken Zusammenhangskomponenten eines gerichteten Graphen $G$ erfolgt effizient in linearer Zeit über ein zweiphasiges Tiefensuchverfahren:

1. Erste DFS-Phase (Topologische Vorsortierung): Führe den Algorithmus rec-DFS auf dem Graphen $G$ aus. Dadurch erhält jeder Knoten $v\in V(G)$ eine eindeutige Post-Order-Markierungsnummer $m(v)\in \{1,\dots ,|V|\}$.
2. Graph-Invertierung: Konstruiere den inversen (gespiegelten) Graphen $G^{\text{rev}}$, indem die Richtung aller Kanten in $E(G)$ exakt umgedreht wird: $E(G^{\text{rev}})=\{(u,v)\mid (v,u)\in E(G)\}$.
3. Zweite DFS-Phase (Komponenten-Schnitt): Führe eine modifizierte Tiefensuche auf dem invertierten Graphen $G^{\text{rev}}$ aus.

• Auswahlreihenfolge: Die Hauptschleife wählt die unbesuchten Startknoten streng in absteigender Reihenfolge ihrer in Phase 1 berechneten Markierungsnummern $m(v)$ (der Knoten mit dem maximalen $m(v)$-Wert startet).

4. Ausgabe: Alle Knoten, die in einem zusammenhängenden Rekursionsaufruf der zweiten Phase in $G^{\text{rev}}$ erreicht werden, bilden exakt eine vollständige starke Zusammenhangskomponente (SCC) von $G$.

Links

• DS_vollständiger_foliensatz.pdf