Einführung
Der Kosaraju-Algorithmus bestimmt Strongly Connected Components (SCCs) in gerichteten Graphen.
In diesem Artikel implementieren wir ihn mit JavaScript und TypeScript und betrachten dabei nicht nur den Code, sondern auch wichtige Implementierungsdetails.
Der Ablauf besteht aus:
DFS auf Originalgraph
↓
Finish Order
↓
Kanten umkehren
↓
DFS auf Transpose Graph
↓
SCCsGraph mit einer Adjazenzliste darstellen
const graph = new Map([
[0, [1]],
[1, [2, 3]],
[2, [0]],
[3, [4]],
[4, [3]]
]);Adjazenzlisten sind besonders für dünn besetzte Graphen geeignet und benötigen typischerweise O(V + E) Speicher.
Erster DFS-Durchlauf
Der Knoten wird erst nach der vollständigen Verarbeitung seiner Nachbarn auf den Stack gelegt:
function fillOrder(node, graph, visited, stack) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor, graph, visited, stack);
}
}
stack.push(node);
}Damit speichern wir die Finish Order und nicht lediglich die Reihenfolge der ersten Besuche.
Transpose Graph erstellen
Jede gerichtete Kante wird umgedreht:
A → Bwird zu:
B → Afunction transposeGraph(graph) {
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
return transpose;
}Vollständige JavaScript-Version
function kosaraju(graph) {
const visited = new Set();
const stack = [];
function fillOrder(node) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
}
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
visited.clear();
const components = [];
function collect(node, component) {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collect(neighbor, component);
}
}
}
while (stack.length > 0) {
const node = stack.pop();
if (!visited.has(node)) {
const component = [];
collect(node, component);
components.push(component);
}
}
return components;
}TypeScript mit Generics
type Graph<T> = Map<T, T[]>;Dadurch können beispielsweise Service-Namen direkt als Vertex verwendet werden.
function kosaraju<T>(graph: Graph<T>): T[][] {
const visited = new Set<T>();
const stack: T[] = [];
const fillOrder = (node: T): void => {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
};
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose: Graph<T> = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor)!.push(node);
}
}
visited.clear();
const components: T[][] = [];
const collect = (node: T, component: T[]): void => {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collect(neighbor, component);
}
}
};
while (stack.length > 0) {
const node = stack.pop()!;
if (!visited.has(node)) {
const component: T[] = [];
collect(node, component);
components.push(component);
}
}
return components;
}Beispiel: Microservice-Abhängigkeiten
const services: Graph<string> = new Map([
["user", ["payment"]],
["payment", ["notification"]],
["notification", ["user"]],
["report", ["analytics"]],
["analytics", ["report"]]
]);Kosaraju kann unter anderem folgende SCCs erkennen:
{user, payment, notification}
{report, analytics}Damit werden zyklische Abhängigkeiten sichtbar.
Komplexität
Die drei Hauptphasen benötigen jeweils lineare Zeit:
DFS 1 O(V + E)
Transpose O(V + E)
DFS 2 O(V + E)Insgesamt:
O(V + E)Auch der Speicherbedarf liegt mit Adjazenzlisten in derselben Größenordnung.
Rekursion in JavaScript
Bei sehr tiefen Graphen kann rekursives DFS einen Stack Overflow verursachen:
RangeError: Maximum call stack size exceededFür sehr große Produktionsgraphen ist daher eine iterative DFS-Implementierung häufig sicherer.
Typische Fehler
Häufige Implementierungsfehler sind:
- Knoten zu früh in den Finish-Stack einfügen.
visitedvor dem zweiten DFS nicht zurücksetzen.- Den zweiten DFS auf dem Originalgraphen ausführen.
- Vertices ohne ausgehende Kanten nicht registrieren.
- Die Reihenfolge innerhalb einer SCC als fest voraussetzen.
Fazit
Kosaraju lässt sich in JavaScript und TypeScript mit einer übersichtlichen Struktur implementieren:
DFS
↓
Finish Order
↓
Transpose
↓
DFS
↓
SCCsMit Adjazenzlisten beträgt die Laufzeit O(V + E).
TypeScript eignet sich besonders für größere Anwendungen, da Generics und Type Safety Graphstrukturen für Module, Packages oder Microservices sauber modellieren können.
Der wichtigste Implementierungsgedanke lautet:
Der erste DFS erzeugt die richtige Reihenfolge, der Transpose Graph kehrt die Erreichbarkeit um und der zweite DFS macht die Grenzen der SCCs sichtbar.