Topologische Sortierung
Jedes Mal, wenn Sie Software installieren, ein Programm bauen oder ein Projekt planen, muss etwas herausfinden, was zuerst zu tun ist. Braucht Aufgabe B die Aufgabe A, muss A früher kommen. Eine topologische Sortierung macht aus einem Geflecht solcher Regeln eine gerade Linie.
Die Idee
Zeichnen Sie jede Aufgabe als Knoten und jede Regel „A vor B“ als Pfeil von A nach B. Eine topologische Reihenfolge ist eine Reihe aller Knoten, in der jeder Pfeil nach rechts zeigt. Sie heißt Sortierung, weil sie Dinge ordnet, aber anders als beim Sortieren von Zahlen muss sie nur die Pfeile beachten: Knoten, die keine Kette von Pfeilen verbindet, dürfen in beliebiger Reihenfolge kommen.
Wann es unmöglich ist
Bilden die Pfeile einen Zyklus, etwa A vor B, B vor C und C vor A, dann müsste A vor sich selbst kommen. Eine topologische Reihenfolge gibt es also genau dann, wenn der Graph keinen gerichteten Zyklus hat. Ein solcher Graph heißt gerichteter azyklischer Graph, kurz DAG. Beide Methoden unten finden einen Zyklus, falls es einen gibt, und taugen damit auch als praktischer Zyklustest.
Ein Beispiel
Nehmen Sie die Pfeile A → C, B → C, B → D, C → E und D → E. Der Kahn-Algorithmus zählt eingehende Pfeile: A und B haben keine, also kommt A zuerst, dann B. Das Entfernen der Pfeile von B macht C und D frei, die folgen, und dann E: die Reihenfolge A, B, C, D, E. Die DFS-Methode besucht A, dann C, dann E; E ist zuerst abgeschlossen, dann C, dann A, und jeder kommt nach vorn. Dann besucht sie B und D, die abgeschlossen werden und davor kommen: die Reihenfolge B, D, A, C, E. Beide Reihenfolgen sind korrekt.
Kahn oder DFS?
Der Kahn-Algorithmus, 1962 von Arthur Kahn veröffentlicht, arbeitet vorwärts: Er weiß immer, welche Aufgaben jetzt beginnen können, was zur Ablaufplanung passt, und er kann unter freien Aufgaben nach jeder Regel wählen, etwa alphabetisch. Die DFS-Methode, 1976 von Robert Tarjan bekannt gemacht, arbeitet von den Enden rückwärts und braucht nur eine Tiefensuche. Bei beiden wächst die Laufzeit mit der Zahl der Knoten plus Kanten.
Anwendungen
Build-Werkzeuge wie make kompilieren Dateien nach den Dateien, von denen sie abhängen. Paketmanager installieren Bibliotheken in der Reihenfolge ihrer Abhängigkeiten. Tabellenkalkulationen berechnen eine Zelle nach den Zellen neu, die ihre Formel nutzt. Universitäten prüfen, ob sich die Voraussetzungen von Kursen erfüllen lassen, Compiler ordnen Befehle, und Datenpipelines führen jeden Schritt aus, sobald seine Eingaben bereit sind. Der Unix-Befehl tsort erledigt allein eine topologische Sortierung.
Selbst ausprobieren
Öffnen Sie die App und drücken Sie Schritt. Die Pfeile sagen, welcher Knoten vor welchem kommen muss. Beim Kahn-Algorithmus zählt die Zahl auf jedem Knoten seine verbleibenden eingehenden Pfeile, und freie Knoten sind blau. Bei der DFS-Methode werden blaue Knoten gerade besucht, und grüne sind eingeordnet. Die Reihenfolge wächst in der Reihe unter dem Graphen. Haken Sie Zyklus hinzufügen an und sehen Sie zu, wie beide Methoden entdecken, dass es keine Reihenfolge gibt.
Häufig gestellte Fragen
Was bedeutet topologisch hier?
Der Name kommt von der Topologie, der Lehre davon, wie Dinge verbunden sind, nicht von ihrer genauen Form. Die Reihenfolge hängt nur davon ab, welche Knoten durch Pfeile verbunden sind, nicht davon, wo sie gezeichnet sind.
Wie finde ich den Zyklus, wenn es keine Reihenfolge gibt?
Die DFS-Methode zeigt ihn direkt: Die Kante zu einem Knoten, der noch besucht wird, bildet zusammen mit dem Weg der gerade besuchten Knoten den Zyklus. Der Kahn-Algorithmus sagt nur, welche Knoten feststecken; eine Suche unter diesen findet den Zyklus.
Kann ich unter den gültigen Reihenfolgen eine bestimmte wählen?
Ja. Sind beim Kahn-Algorithmus mehrere Knoten frei, nehmen Sie den, den Sie bevorzugen, zum Beispiel den kleinsten Buchstaben oder die dringendste Aufgabe. Mit einer Prioritätswarteschlange erhalten Sie die alphabetisch erste Reihenfolge.
Wie hilft die topologische Sortierung bei kürzesten Wegen?
Auf einem gerichteten azyklischen Graphen findet man alle kürzesten Wege von einem Start in einem einzigen Durchlauf, wenn man die Kanten jedes Knotens in topologischer Reihenfolge prüft und verbessert, sogar mit negativen Kanten, schneller als mit Dijkstra oder Bellman–Ford.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Topologische Sortierung ausprobieren