Ein DAG (englisch directed acyclic graph, deutsch gerichteter azyklischer Graph) ist ein gerichteter Graph, der keinen Zyklus enthält. Es gibt also keinen Pfad, der über gerichtete Kanten zum Ausgangsknoten zurückführt. Genau diese Zyklenfreiheit macht DAGs zum Standardmodell für Abhängigkeiten.
Beispiele aus der Praxis
- Build-Systeme: Zuerst werden Abhängigkeiten kompiliert, dann das Modul selbst
- Paketmanager: Ein Paket hängt von anderen Paketen ab — nie kreuzweise
- CI/CD-Pipelines: Stages laufen in fester, azyklischer Reihenfolge
- Datenfluss-Graphen in Planungs- und Analysesystemen
- Transaktionsgraphen moderner Kryptowährungen
Eigenschaften
Ein DAG besitzt immer mindestens eine topologische Sortierung: eine Anordnung aller Knoten, in der jede Kante von links nach rechts verläuft. Das erlaubt eine Abarbeitung ohne Rückwärtssprünge. Mindestens ein Knoten hat den Eingangsgrad 0 (eine Quelle), mindestens einer den Ausgangsgrad 0 (eine Senke).
Algorithmen auf DAGs
- Topologische Sortierung nach Kahn oder per Tiefensuche — ein gefundener Zyklus zeigt eine fehlerhafte Abhängigkeit
- Längster Pfad (kritischer Pfad) für Projekt- und Build-Planung
- Dynamische Programmierung entlang der topologischen Ordnung
Abgrenzung: Ein gerichteter Graph MIT Zyklus ist kein DAG — zyklische Abhängigkeiten (etwa A braucht B, B braucht A) führen in Build- oder Deployment-Systemen zu Endlosschleifen und müssen aufgelöst werden. Die Zusammenhangskomponenten eines DAG lassen sich per Breitensuche ermitteln; Knoten und Kanten sind die Bausteine.
Verwandte Grundlagen: Graph-Datenstruktur.