Nächste Seite: Zweifach zusammenhängende Komponenten Aufwärts: Bäume Vorherige Seite: Tiefensuche auf ungerichteten Graphen
Def: Ein gerichteter kreisfreier Graph heißt DAG (directed acyclic graph).
Satz: Ein gerichteter Graph ist genau dann ein DAG, wenn die Tiefensuche keine Rückwärtskante erzeugt.
Implementierung: wie Tiefensuche,
mit zusätzlichem Feld verlassen