- Aktuell
- Frei oder wird besucht
- Eingeordnet
- Zyklus
Topologische Sortierung
Socken vor Schuhen, Fundament vor Mauern, ein Kurs vor dem Kurs, der ihn voraussetzt. Eine topologische Sortierung bringt die Knoten eines Graphen mit Einbahnkanten in eine Reihe, in der jede Kante nach vorn zeigt. Wählen Sie den Kahn-Algorithmus oder die DFS-Methode, gehen Sie Schritt für Schritt vor, um die Reihenfolge wachsen zu sehen, und fügen Sie einen Zyklus hinzu, um zu sehen, warum dann keine Reihenfolge möglich ist. Drücken Sie Abspielen, um zuzusehen, wie die Reihenfolge wächst, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Jede Kante ist eine Einbahnstraße, wie ihr Pfeil zeigt: Lesen Sie sie als „dies kommt vor dem“. Wählen Sie die Methode: Der Kahn-Algorithmus ordnet zuerst Knoten ohne eingehende Kanten ein, und die Zahl auf jedem Knoten gibt an, wie viele eingehende Kanten er noch hat; die DFS-Methode setzt jeden Knoten nach vorn, sobald alles nach ihm eingeordnet ist. Die Reihe unter dem Graphen ist die bisherige Reihenfolge. Haken Sie Zyklus hinzufügen an, um zu sehen, wie jede Methode einen findet. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie den Kahn-Algorithmus oder die DFS-Methode.
- Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen.
- Beobachten Sie, wie die Reihenfolge unter dem Graphen wächst. Haken Sie Zyklus hinzufügen an, um zu sehen, wie jede Methode einen findet.
Kahn-Algorithmus
Zählen Sie für jeden Knoten, wie viele Kanten auf ihn zeigen. Ein Knoten ohne solche Kanten hängt von nichts ab und kann zuerst kommen. Ordnen Sie einen solchen Knoten ein und entfernen Sie seine ausgehenden Kanten: Die Knoten, auf die sie zeigten, haben nun eine eingehende Kante weniger, und manche erreichen null und werden frei. Ordnen Sie weiter freie Knoten ein, bis keiner mehr übrig ist. Wurden manche Knoten nie frei, warten sie in einem Zyklus aufeinander, und es gibt keine topologische Reihenfolge.
Die DFS-Methode
Starten Sie eine Tiefensuche von jedem noch nicht besuchten Knoten. Ein Knoten ist abgeschlossen, wenn alles, was von ihm aus erreichbar ist, abgeschlossen ist; also ist alles, was nach ihm kommen muss, schon eingeordnet. Setzen Sie jeden abgeschlossenen Knoten vorn in die Reihenfolge, und die Reihenfolge stimmt. Folgt die Suche einer Kante zu einem Knoten, in dem sie sich noch befindet, schließt diese Kante einen Zyklus, und wieder gibt es keine Reihenfolge.
Häufig gestellte Fragen
Was ist eine topologische Sortierung?
Eine Anordnung der Knoten eines gerichteten Graphen, in der jede Kante von einem früheren zu einem späteren Knoten führt. Bedeuten die Kanten „muss vorher kommen“, ist es eine Reihenfolge, in der sich alle Aufgaben erledigen lassen.
Wann gibt es eine topologische Reihenfolge?
Genau dann, wenn der Graph keinen gerichteten Zyklus hat: Er ist ein gerichteter azyklischer Graph, kurz DAG. Bei einem Zyklus müsste jeder Knoten darauf vor sich selbst kommen.
Ist die topologische Reihenfolge eindeutig?
Meist nicht. Wenn zwei Knoten nicht durch eine Kette von Kanten verbunden sind, kann jeder von beiden zuerst kommen, also kann ein Graph viele gültige Reihenfolgen haben. Der Kahn-Algorithmus und die DFS-Methode liefern oft verschiedene.
Wie schnell ist eine topologische Sortierung?
Beide Methoden betrachten jeden Knoten und jede Kante eine feste Anzahl von Malen, also wächst der Aufwand mit der Zahl der Knoten plus der Zahl der Kanten.
Wird mein Graph irgendwohin gesendet?
Nein. Der Graph wird in Ihrem Browser erzeugt und sortiert, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor