Strongly Connected Components (SCCs) sind ein zentrales Konzept in gerichteten Graphen. Ein SCC ist eine maximale Menge von Knoten, in der jeder Knoten jeden anderen über gerichtete Pfade erreichen kann.

Für zwei Knoten u und v im selben SCC gilt:

u ~> v
v ~> u

Erreichbarkeit ist nicht gleich starke Zusammenhangskomponente

Bei:

A -> B -> C

ist C von A aus erreichbar. Der Rückweg von C nach A muss aber nicht existieren. Deshalb gehören A und C nicht automatisch zum selben SCC.

Bei einem Zyklus wie:

A -> B -> C
^         |
|_________|

kann dagegen jeder Knoten jeden anderen erreichen. {A, B, C} bildet daher ein SCC.

Warum sind SCCs praktisch wichtig?

Typische Einsatzgebiete sind:

• Circular Dependencies zwischen Softwaremodulen
• Abhängigkeiten zwischen Microservices
• Call-Graph- und Control-Flow-Analyse
• gerichtete soziale Netzwerke
• State Machines
• Build-Systeme und Package Manager
• Komprimierung großer gerichteter Graphen

Kosaraju und Tarjan

Zwei klassische Algorithmen sind:

1. Kosaraju
2. Tarjan

Beide arbeiten in:

O(V + E)

Kosaraju ist oft leichter zu verstehen, weil der Algorithmus zwei DFS-Durchläufe und einen umgekehrten Graphen verwendet.

Wie funktioniert Kosaraju?

Kosaraju besteht aus drei Schritten:

1. DFS auf dem Originalgraphen und Speichern der Abschlussreihenfolge.
2. Umkehren aller Kanten.
3. DFS auf dem umgekehrten Graphen in absteigender Abschlussreihenfolge.

Jeder neue DFS-Baum im dritten Schritt entspricht genau einem SCC.

Warum funktioniert das?

Wenn jedes SCC zu einem Superknoten zusammengefasst wird, entsteht der sogenannte Condensation Graph. Dieser Graph ist immer ein DAG.

Würde zwischen den komprimierten SCCs ein Zyklus existieren, könnten sich diese Komponenten gegenseitig erreichen und müssten eigentlich zu einem größeren SCC gehören.

Die erste DFS liefert eine geeignete Reihenfolge. Nach dem Umdrehen der Kanten kann die zweite DFS die Komponenten einzeln isolieren.

JavaScript-Implementierung

function kosaraju(graph) {
  const visited = new Set();
  const order = [];
  const nodes = new Set(Object.keys(graph));

  for (const neighbors of Object.values(graph)) {
    for (const node of neighbors) nodes.add(node);
  }

  function dfs1(node) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) dfs1(next);
    }

    order.push(node);
  }

  for (const node of nodes) {
    if (!visited.has(node)) dfs1(node);
  }

  const reversed = {};

  for (const node of nodes) reversed[node] = [];

  for (const [from, neighbors] of Object.entries(graph)) {
    for (const to of neighbors) reversed[to].push(from);
  }

  visited.clear();
  const components = [];

  function dfs2(node, component) {
    visited.add(node);
    component.push(node);

    for (const next of reversed[node] ?? []) {
      if (!visited.has(next)) dfs2(next, component);
    }
  }

  while (order.length) {
    const node = order.pop();

    if (!visited.has(node)) {
      const component = [];
      dfs2(node, component);
      components.push(component);
    }
  }

  return components;
}

Praxisbeispiel: zyklische Abhängigkeiten

Auth -> User
User -> Payment
Payment -> Auth

Diese drei Module bilden einen Dependency-Zyklus und werden durch SCC-Analyse als eine zusammengehörige Komponente erkannt.

Condensation Graph

Aus:

S1 = {A, B, C}
S2 = {D, E}
S3 = {F}

kann beispielsweise werden:

S1 -> S2 -> S3

Das ist ein DAG und kann für Scheduling, Dependency Analysis oder weitere Graphalgorithmen wesentlich einfacher verarbeitet werden.

Komplexität

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

Der zusätzliche Speicher wird vor allem für den umgekehrten Graphen, visited-Strukturen, die Abschlussreihenfolge und das Ergebnis benötigt.

Wichtige Sonderfälle

• Ein isolierter Knoten ist allein ein SCC.
• Ein Self-Loop ergibt weiterhin ein SCC mit einem Knoten.
• Ist der gesamte Graph stark zusammenhängend, existiert genau ein SCC.
• In einem DAG ist jeder Knoten sein eigenes SCC.

SCC vs. Zyklenerkennung

Ein SCC mit mehr als einem Knoten enthält mindestens einen gerichteten Zyklus. SCC-Zerlegung ist aber umfassender als Cycle Detection: Sie partitioniert den gesamten Graphen in maximale gegenseitig erreichbare Bereiche.

Wann sollte man SCC verwenden?

SCCs sind geeignet, wenn Fragen auftreten wie:

• Welche Knoten können sich gegenseitig erreichen?
• Welche Dependencies bilden Zyklen?
• Welche Module oder Services sind eng gekoppelt?
• Wie lässt sich ein gerichteter Graph zu einem DAG komprimieren?
• Welche Zustände einer State Machine gehören zu wiederkehrenden Bereichen?

Fazit

Kosaraju lässt sich so merken:

DFS + Finishing Order
        ↓
Kanten umdrehen
        ↓
DFS in umgekehrter Reihenfolge
        ↓
SCCs

Das eigentliche Ziel besteht darin, zyklische und gegenseitig erreichbare Strukturen in gerichteten Systemen sichtbar zu machen.