Topologische Sortierung erklärt, mit Code

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Was ist eine topologische Sortierung?

Eine topologische Sortierung ist eine lineare Anordnung der Knoten eines gerichteten azyklischen Graphen (DAG), sodass für jede gerichtete Kante von u nach v der Knoten u vor dem Knoten v steht. Einfach gesagt: alles so aufreihen, dass jeder Pfeil nach vorne zeigt.

In dieser Definition stecken zwei Bedingungen. Der Graph muss gerichtet sein (Abhängigkeiten haben eine Richtung: A vor B ist nicht dasselbe wie B vor A) und azyklisch (keine Zyklen). Wenn A vor B und B vor A kommen muss, kann keine gültige Reihenfolge existieren. Bäume und DAGs sind hier nahe Verwandte; zur Baumseite siehe gewurzelte Bäume.

Wann Sie sie brauchen

Die topologische Sortierung ist die Antwort, sobald ein Problem klingt wie "erledige diese Dinge in einer Reihenfolge, die ihre Voraussetzungen respektiert". Sie erkennen es an diesen Signalen:

• Abhängigkeiten: "Aufgabe X erfordert, dass Aufgabe Y zuerst fertig ist."
• Anordnung oder Ablaufplanung: "In welcher Reihenfolge kann ich diese Kurse belegen?"
• Bauen und Kompilieren: "Module so kompilieren, dass jeder Import bereits existiert."
• Auflösung: "Pakete so installieren, dass jede Abhängigkeit vor dem installiert wird, was sie braucht."

Sie ist eines der häufigsten Muster in technischen Interviews, weshalb sie im Leitfaden zu Graphenalgorithmen für Programmierinterviews vorkommt und eine Etappe des Graphentheorie-Lernpfads bildet.

Kahns Algorithmus, Schritt für Schritt

Die intuitivste Methode ist Kahns Algorithmus. Er stützt sich auf eine Zahl pro Knoten: den Eingangsgrad, die Anzahl der eingehenden Kanten. Ein Knoten mit Eingangsgrad 0 hat keine offenen Voraussetzungen, kann also gefahrlos als Nächstes platziert werden.

Die Schleife ist einfach: Nimm einen beliebigen Knoten mit Eingangsgrad 0, gib ihn aus und entferne seine ausgehenden Kanten, was die Eingangsgrade seiner Nachbarn senkt. Wiederhole, bis nichts mehr übrig ist. Lassen wir das auf diesem DAG laufen. Jeder Knoten trägt seine Position in einer gültigen Reihenfolge.

Hier ist der Ablauf. Die Warteschlange enthält Knoten, deren Eingangsgrad 0 erreicht hat. Wir beginnen mit A, dem einzigen Knoten, der von nichts abhängt.

Beachten Sie: Nach dem Nehmen von A fiel der Eingangsgrad von B und C gleichzeitig auf 0. Beide könnten als Nächstes folgen, und genau deshalb hat ein DAG meist viele gültige Reihenfolgen. Die Eingangsgrade auf einem Live-Graphen fallen zu sehen, macht es greifbar, was Sie im Algorithmen-Visualisierer ausprobieren können.

Implementierung in Python

Kahns Algorithmus lässt sich fast direkt in Code übersetzen. Wir berechnen jeden Eingangsgrad, füllen eine Warteschlange mit den Knoten vom Eingangsgrad null und leeren sie.

from collections import deque, defaultdict

def topological_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for u, v in edges:          # Kante u -> v bedeutet u vor v
        graph[u].append(v)
        in_degree[v] += 1

    # Mit jedem Knoten starten, der keine Voraussetzungen hat.
    queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1        # die Kante entfernen
            if in_degree[neighbour] == 0:    # keine Voraussetzungen mehr
                queue.append(neighbour)

    # Erreichte ein Knoten nie Eingangsgrad 0, hat ein Zyklus ihn blockiert.
    if len(order) == num_nodes:
        return order
    return []   # Zyklus erkannt, keine gültige Reihenfolge

Die abschließende Prüfung ist der elegante Teil: Fehlt in der Ausgabe ein Knoten, sind diese Knoten in einem Zyklus gefangen. Derselbe Code, der einen DAG ordnet, erkennt also auch, ob der Graph überhaupt ein DAG war.

Der DFS-Ansatz

Es gibt eine zweite klassische Methode, die auf der Tiefensuche beruht. Führen Sie DFS aus, und wenn ein Knoten abschließt (alle seine Nachfahren sind erkundet), legen Sie ihn auf einen Stapel. Die topologische Reihenfolge ist der Stapel, rückwärts gelesen.

Die Intuition: Ein Knoten schließt erst ab, nachdem alles, worauf er zeigt, abgeschlossen ist, sodass er in umgekehrter Abschlussreihenfolge vor all seinen Nachfahren landet. Die DFS-Variante braucht keine Eingangsgrad-Buchführung, doch Sie müssen dennoch gegen Zyklen absichern, indem Sie Knoten auf dem aktuellen Rekursionspfad verfolgen. Beide Ansätze sind gleichermaßen gültig; Kahns lässt sich meist leichter durchdenken, während DFS kompakter ist.

Zyklen und warum sie sie brechen

Eine topologische Reihenfolge existiert genau dann, wenn der Graph azyklisch ist. Der Grund ist unmittelbar: Ein Zyklus A → B → A verlangt, dass A vor B und B vor A steht, zugleich, was in einer Linie unmöglich ist.

Die nützliche Folge: Die topologische Sortierung ist auch ein Zyklendetektor. Können Sie in Kahns Algorithmus nicht alle V Knoten ausgeben, bilden die übrigen Knoten mindestens einen Zyklus. In der DFS-Variante signalisiert das Antreffen eines Knotens, der bereits auf Ihrem aktuellen Pfad liegt, einen Zyklus.

Deshalb löst man Interviewfragen im Stil von "Kursplan", die eigentlich fragen "ist das überhaupt möglich?", mit einer topologischen Sortierung.

Komplexität

Beide Algorithmen sind optimal: Sie berühren jeden Knoten und jede Kante genau einmal.

Diese lineare Kosten sind der Grund, warum die topologische Sortierung auf riesige Abhängigkeitsgraphen skaliert. Wie sie sich gegen jeden anderen Graphenalgorithmus schlägt, sehen Sie im Komplexitätsleitfaden und im einseitigen Spickzettel.

Anwendungen in der Praxis

• Build-Systeme: Make, Bazel und Co. sortieren Ziele topologisch, damit Abhängigkeiten zuerst gebaut werden.
• Paketmanager: npm, pip und apt ermitteln die Installationsreihenfolge aus einem Abhängigkeits-DAG.
• Aufgaben- und Job-Planung: Tabellenkalkulationen, die Zellen neu berechnen, CI-Pipelines, die Stufen ordnen, Kursplaner.
• Compiler: Deklarationen ordnen und Ausdrücke auswerten, sodass jedes Symbol vor der Verwendung definiert ist.