Was ist der Kosaraju-Algorithmus und welches Problem löst er?

Einführung

Viele Graphalgorithmen wirken zunächst kompliziert, lösen aber häufig ein sehr verständliches Problem. Der Kosaraju-Algorithmus ist ein gutes Beispiel dafür.

Er wird verwendet, um Strongly Connected Components, kurz SCCs, in einem gerichteten Graphen zu finden.

In diesem Artikel beginnen wir bewusst nicht mit mathematischen Beweisen oder Code, sondern mit dem Problem selbst.

Was ist ein Graph?

Ein Graph besteht aus Knoten und Verbindungen zwischen diesen Knoten.

Beispiel:

A --- B
|     |
C --- D

Graphen modellieren unter anderem:

• soziale Netzwerke
• Straßennetze
• Serverkommunikation
• Softwareabhängigkeiten
• Links zwischen Webseiten
• Kontrollfluss in Programmen
• Beziehungen zwischen Microservices

Was ist ein gerichteter Graph?

In einem gerichteten Graphen besitzt jede Kante eine Richtung.

A → B

bedeutet, dass ein Weg von A nach B existiert. Daraus folgt jedoch nicht automatisch, dass man auch von B nach A gelangen kann.

In einer Softwarearchitektur kann etwa:

Service A → Service B

bedeuten, dass Service A von Service B abhängig ist.

Wo liegt das eigentliche Problem?

Betrachten wir:

A → B → C
↑       ↓
└───────┘

D → E

Von A gelangen wir zu B, von B zu C und von C wieder zurück zu A.

Damit bilden:

{A, B, C}

eine besonders stark verbundene Gruppe.

Dagegen können wir zwar von D nach E gelangen, aber nicht wieder von E nach D zurück.

Was bedeutet Strongly Connected?

Zwei Knoten u und v sind stark zusammenhängend, wenn sowohl ein Pfad

u → ... → v

als auch ein Pfad

v → ... → u

existiert.

Beide Knoten müssen sich also gegenseitig erreichen können.

Was ist eine Strongly Connected Component?

Eine Strongly Connected Component ist eine maximale Gruppe von Knoten, innerhalb der jeder Knoten jeden anderen erreichen kann.

Zum Beispiel:

A → B → C
↑       ↓
└───────┘

D → E → F
↑       ↓
└───────┘

enthält zwei SCCs:

SCC 1 = {A, B, C}
SCC 2 = {D, E, F}

Was macht der Kosaraju-Algorithmus?

Kosaraju findet alle SCCs eines gerichteten Graphen.

Für:

A → B
B → C
C → A
C → D
D → E
E → D

liefert er beispielsweise:

SCC 1 = {A, B, C}
SCC 2 = {D, E}

Vereinfacht gesagt:

Kosaraju zerlegt einen gerichteten Graphen in maximale Gruppen von Knoten, die sich gegenseitig über gerichtete Pfade erreichen können.

Warum sind SCCs wichtig?

Zirkuläre Softwareabhängigkeiten

Module A → Module B
Module B → Module C
Module C → Module A

Diese Module bilden eine zirkuläre Abhängigkeit und gehören zu derselben SCC.

Microservices

Abhängigkeitszyklen zwischen Services können durch SCC-Analyse sichtbar gemacht werden.

Soziale Netzwerke

Follower-Beziehungen lassen sich als gerichtete Kanten modellieren. SCCs beschreiben dann Bereiche mit gegenseitiger Erreichbarkeit.

Webgraphen

Webseiten sind Knoten und Hyperlinks gerichtete Kanten. SCCs können stark miteinander verlinkte Bereiche identifizieren.

Compiler und Programmanalyse

Control-Flow-, Call- und Dependency-Graphen enthalten häufig Zyklen. SCCs helfen bei der strukturellen Analyse solcher Graphen.

Package-Management

Auch zyklische Abhängigkeiten zwischen Bibliotheken und Paketen lassen sich mit SCC-Verfahren analysieren.

Warum reicht normales DFS nicht aus?

Betrachten wir:

A → B → C

Ein DFS von A besucht alle drei Knoten.

Trotzdem gehören sie nicht zu derselben SCC, weil C weder B noch A erreichen kann.

Daher gilt:

Reachability ≠ Strong Connectivity

Kosaraju löst genau dieses Problem.

Die Grundidee von Kosaraju

Auf hoher Ebene arbeitet der Algorithmus in drei Schritten:

1. DFS auf dem ursprünglichen Graphen und Speichern der Abschlussreihenfolge.
2. Umkehren aller Kanten und Erzeugen des Transpose Graph.
3. Erneutes DFS auf dem transponierten Graphen in einer speziellen Reihenfolge.

Schematisch:

Original Graph
      ↓
     DFS
      ↓
Finish Order
      ↓
Transpose Graph
      ↓
     DFS
      ↓
     SCCs

Jeder DFS-Durchlauf in der zweiten Phase identifiziert eine SCC.

Einfaches Beispiel

A → B → C
↑       ↓
└───────┘

C → D
D → E
E → D

Hier erhalten wir:

SCC 1 = {A, B, C}
SCC 2 = {D, E}

C kann D erreichen, aber D und E können nicht zu A, B oder C zurückkehren. Deshalb bleiben die Komponenten getrennt.

Zeitkomplexität

Mit einer Adjazenzlisten-Darstellung beträgt die Laufzeit:

O(V + E)

Dabei ist:

• V die Anzahl der Knoten.
• E die Anzahl der Kanten.

Damit ist Kosaraju auch für große Graphen effizient.

Gibt es Alternativen?

Ja. Bekannte Alternativen sind:

• Tarjan's Algorithm
• Gabow's Algorithm

Auch Tarjan läuft in O(V + E). Kosaraju ist jedoch aufgrund seines übersichtlichen Aufbaus häufig besonders gut zum Lernen geeignet.

Wann sollte man an Kosaraju denken?

Typische Hinweise in einer Aufgabenstellung sind:

• Strong Connectivity
• Mutual Reachability
• Circular Dependency
• zyklische Module
• zyklische Services
• Komponenten eines gerichteten Graphen

Dann ist SCC-Analyse häufig der richtige Ansatz.

Cycle und SCC sind nicht dasselbe

Ein Cycle ist ein geschlossener Pfad wie:

A → B → C → A

Eine SCC dagegen ist eine maximale Menge gegenseitig erreichbarer Knoten.

Eine SCC kann mehrere unterschiedliche Zyklen enthalten.

Fazit

Der Kosaraju-Algorithmus findet Strongly Connected Components in gerichteten Graphen.

SCCs treten unter anderem bei Softwareabhängigkeiten, Microservices, sozialen Netzwerken, Compilern, Webgraphen und Package-Systemen auf.

Kosaraju verwendet zwei DFS-Phasen und einen transponierten Graphen und erreicht mit Adjazenzlisten eine Laufzeit von O(V + E).

Die wichtigste Idee lautet:

Kosaraju sucht nicht lediglich nach einzelnen Zyklen, sondern zerlegt einen gerichteten Graphen in maximale Gruppen gegenseitig erreichbarer Knoten.

Im nächsten Artikel betrachten wir Strongly Connected Components genauer, bevor wir den Ablauf von Kosaraju Schritt für Schritt analysieren.