Overview
Topologische Sortierung ordnet Knoten eines DAGs so, dass jede Kante von früher nach später zeigt.
Analogy
Kursvoraussetzungen: Mathematik muss vor Lineare Algebra abgeschlossen werden.
Step-by-step
- Kahns BFS: Eingangsgrade berechnen; 0-Eingangsgrad-Knoten in Queue; verarbeiten, Nachbarn dekrementieren.
- DFS Postorder: DFS ausführen; Knoten nach allen Nachkommen in Ergebnis-Stack schieben.
- DFS-Stack umkehren für topologische Reihenfolge.
- Wenn Zyklus vorhanden: Kahns Algorithmus verarbeitet nicht alle Knoten.
Visual
DAG: A→B→C, A→C. Eingangsgrade: A=0,B=1,C=2. Verarbeite A→B→C.
Common mistakes
- Auf Graph mit Zyklen ausführen (Ergebnis würde Knoten auslassen oder ungültig sein).
- Zyklus nicht erkennen (Zyklus = nicht alle Knoten in Kahn verarbeitet).
Practice questions
- Build-Reihenfolge für Liste von Abhängigkeiten finden.
- Kursplan auf Machbarkeit prüfen.