Topologische Reihenfolge

→ Gerichtete Graphen und Darstellung
→ DFS

Definition

Reihenfolge, die alle Abhängigkeiten erfüllt. z.B. richtige Reihenfolge beim Anziehen. Ordnet man Knoten nach dieser Reihenfolge an, so zeigen alle Kanten von links nach rechts.

Wenn eine Kante von Knoten u zu Knoten v zeigt, muss u vor v stehen.

Topologische Reihenfolge ist nicht immer möglich, Gegenbeispiel gerichteter Zyklus. Hier hat jeder Knoten einen Nachfolger, kann nicht enden.

$\exists \text{ topologische Reihenfolge} \Longleftrightarrow \nexists \text{ gerichteter Zyklus}$

Topologisch Sortieren

• finde Senke v durch den Path-Algorithmus (siehe unten)
• setze v an letzte Stelle
• entferne v und löse Rest rekursiv (finde neue Senke nachdem v entfernt wurde, etc.)

Path-Algorithmus, Version 1

Link zur Vorlesung

Path(u):
    markiere Knoten u 
    if ∃ unmarkierter Nachfolger v: 
        Path(v)

• Path(u) markiert Pfad P mit Start u
• Endknoten v von P hat alle Nachfolger markiert, v ist Senke, wenn $\nexists$ gerichteter Zyklus
• Von unten nach oben ablesen (immer die gefundene Senken werden ja ganz hinten hingestellt)

Ineffizient, da “wiederholtes Laufen”, besser: “bereits entdeckten Pfad so weit wie möglich wiederverwenden”

Version 2, Depth-First-Search

→ siehe DFS