Starke Zusammenhangskomponenten: Gegenseitige Erreichbarkeit in gerichteten Graphen

Starke Zusammenhangskomponenten (englisch: strongly connected components, kurz SCC) sind die „Inseln gegenseitiger Erreichbarkeit“ eines gerichteten Graphen: Zwei Knoten u und v gehören derselben Komponente an, wenn ein Weg von u nach v und ein Weg von v nach u existiert. Jeder gerichtete Graph zerfällt eindeutig in solche Komponenten.

Definition

  • Zwei Knoten sind stark zusammenhängend, wenn jeder den anderen erreichen kann — Erreichbarkeit in beide Richtungen.
  • Eine starke Zusammenhangskomponente ist eine maximale Menge von Knoten, in der jedes Knotenpaar stark zusammenhängend ist.
  • Der Unterschied zur gewöhnlichen Zusammenhangskomponente: Dort zählt Erreichbarkeit im ungerichteten Sinn (Kantenrichtung egal), bei SCCs zählt die Richtung. Ein Graph kann also schwach zusammenhängend sein und trotzdem viele kleine SCCs enthalten.
  • Beispiel: Bei Einbahnstraßen gehören zwei Stadtteile genau dann derselben SCC an, wenn man von jedem aus den jeweils anderen erreichen kann.

Der Kondensationsgraph

Zieht man jede SCC zu einem einzigen Knoten zusammen, entsteht der Kondensationsgraph. Er ist immer azyklisch, also ein DAG — denn Zyklen zwischen zusammengezogenen Komponenten würden sie ja zu einer größeren SCC vereinen. Damit existiert auf ihm stets eine topologische Sortierung, und viele Algorithmen arbeiten danach nur noch auf dem kleineren DAG weiter.

Algorithmen in O(V + E)

Beide Standardverfahren basieren auf der Tiefensuche und laufen in linearer Zeit.

Kosaraju (1978):

1. DFS auf G, merke Endzeit finish[u] für jeden Knoten
2. Kehre alle gerichteten Kanten um → Graph G^T
3. DFS auf G^T in absteigender finish-Reihenfolge
   → jeder neu gestartete Suchbaum ist eine SCC

Tarjan (1972): Ein einziger DFS-Lauf mit Index- und Lowlink-Werten plus Stack:

DFS(u):
    index[u] = lowlink[u] = zähler++
    pushe u auf den Stack
    for v in Nachbarn von u:
        if v noch nicht besucht:
            DFS(v)
            lowlink[u] = min(lowlink[u], lowlink[v])
        elif v liegt auf dem Stack:
            lowlink[u] = min(lowlink[u], index[v])
    if lowlink[u] == index[u]:
        alle Knoten vom Stack bis u bilden eine SCC

Implementieren lässt sich beides mit einer Adjazenzliste oder Adjazenzmatrix.

Anwendungen

  • Deadlock-Erkennung: In einem Wartegraphen, in dem Prozesse auf Ressourcen warten, weist eine SCC mit mehr als einem Knoten (oder eine Selbstschleife) auf einen möglichen Deadlock hin.
  • Compiler: Abhängigkeitsanalyse, Erkennung von Schleifen (starke Schleifen) und eine sinnvolle Bearbeitungsreihenfolge.
  • 2-SAT: Ein 2-SAT-Problem ist genau dann erfüllbar, wenn keine Variable und ihre Negation in derselben SCC liegen.
  • Soziale Netzwerke: Eng verbundene Gruppen und Communities.
  • Web-Graph: SCCs als dichte Kernregionen des Linknetzes.
  • Reduktion auf den azyklischen Kondensationsgraphen für weitere Berechnungen.

Abgrenzung

Während die Zusammenhangskomponente für ungerichtete Graphen definiert ist, spielt bei SCCs die Richtung der Kanten die entscheidende Rolle — sie sind das passende Konzept für gerichtete Graphen. Grundlagen zu Knoten, Kanten und Speicherung liefert die Graph-Datenstruktur.