Topological Sorting: Kahn, DFS und Abhängigkeiten in DAGs

Topological Sorting erzeugt eine lineare Reihenfolge der Knoten eines gerichteten Graphen, sodass für jede Kante:

u → v

u vor v steht.

Eine solche Reihenfolge existiert nur für einen Directed Acyclic Graph (DAG).

Kahn-Algorithmus

Kahn verwendet den in-degree.

1. In-Degree aller Knoten berechnen.
2. Alle Knoten mit In-Degree 0 in eine Queue legen.
3. Einen Knoten entnehmen.
4. In-Degree seiner Nachfolger reduzieren.
5. Neue Null-Knoten einfügen.
6. Werden nicht alle Knoten verarbeitet, existiert ein Zyklus.

function topoSort(graph) {
  const nodes = new Set();
  const indegree = new Map();

  for (const [u, list] of Object.entries(graph)) {
    nodes.add(u);
    for (const v of list) nodes.add(v);
  }

  for (const n of nodes) indegree.set(n, 0);

  for (const list of Object.values(graph)) {
    for (const v of list) {
      indegree.set(v, indegree.get(v) + 1);
    }
  }

  const queue = [...nodes].filter(
    n => indegree.get(n) === 0
  );

  let head = 0;
  const order = [];

  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);

    for (const v of graph[u] ?? []) {
      indegree.set(v, indegree.get(v) - 1);

      if (indegree.get(v) === 0) {
        queue.push(v);
      }
    }
  }

  return order.length === nodes.size
    ? order
    : null;
}

DFS-Methode

Alternativ kann DFS mit Postorder und umgekehrter Finish-Reihenfolge verwendet werden.

Für produktiven Code ist Cycle Detection mit den Zuständen unvisited, visiting, finished wichtig.

Mehrere gültige Reihenfolgen

Eine topologische Reihenfolge muss nicht eindeutig sein. Unabhängige Tasks können ihre Position tauschen.

Anwendungen

• Build-Reihenfolgen
• Kursvoraussetzungen
• Package Dependencies
• CI/CD
• Workflows
• ETL Pipelines
• Migrationen
• DAG Dynamic Programming

Komplexität

O(V + E)

Fazit

Topological Sorting löst Abhängigkeitsreihenfolgen in DAGs und erkennt zusammen mit Kahn oder DFS auch zyklische, damit ungültige Dependency-Strukturen.