Motivation

Eine topologische Sortierung existiert nur, wenn der Graph keine Zyklen hat. Wir erstellen eine mit Kahns Algorithmus, der wiederholt einen Knoten entfernt, der keine verbleibenden eingehenden Kanten hat.

Warum sollte man die topologische Sortierung lernen?

• Reihenfolge mit Einschränkungen: Build-Systeme, Aufgabenplanung, Kursvoraussetzungen und die Neuberechnung von Tabellenkalkulationen basieren alle darauf.
• Zyklenerkennung: Wenn man nicht jeden Knoten ordnen kann, muss der Graph einen Zyklus enthalten.
• Grundlage für DAG-Algorithmen: Kürzeste und längste Pfade in einem DAG werden in topologischer Reihenfolge berechnet.

Es können viele gültige Reihenfolgen existieren. Um eine vorhersehbare Antwort zu erhalten, entfernen wir immer den Knoten mit der kleinsten Nummer, dessen In-Degree (Eingangsgrad) 0 ist.