Ein gerichteter Azyklischer Graph (DAG) ist ein Diagrammtyp, bei dem es unmöglich ist, durch Durchlaufen der Kanten zum selben Knoten zurückzukehren.

In der Graphentheorie ist ein Graph eine Struktur, die aus Knoten besteht, die durch Kanten verbunden sind. Sie können sich die Knoten als Punkte und die Kanten als Linien vorstellen, die von Punkt zu Punkt gezogen werden.

‚Gerichtet‘ bedeutet, dass sich die Kanten des Graphen nur in eine Richtung bewegen, wobei zukünftige Kanten von vorherigen abhängen. Wenn Sie beispielsweise den Prozess des Kochens und Essens einer Mahlzeit aus Reis und Hühnchen grafisch darstellen möchten, müssen die damit verbundenen Aufgaben topologisch geordnet (oder topologisch sortiert) sein. Bevor Sie die Mahlzeit essen können, müssen Sie das Essen zubereiten, damit der Rand notwendigerweise von der Zubereitung bis zum Essen gerichtet ist. Aber bevor Sie das Essen zubereiten können, müssen Sie die Zutaten kaufen, also muss der Rand wieder von der früheren Veranstaltung zur späteren Veranstaltung gehen. Angenommen, der Reis wurde in einem vom Huhn getrennten Ereignis gekauft, gäbe es zwei separate Kanten für die Lebensmitteleinkaufsereignisse, die nicht miteinander verbunden sind, sondern beim Zubereiten des Essens zusammenlaufen.

‚Azyklisch‘ bedeutet, dass es unmöglich ist, an einem Punkt des Graphen zu beginnen und zu ihm zurückzukehren, indem man den Kanten folgt. Während ein Zyklus wie ein Kreis zu seinem ursprünglichen Ausgangspunkt zurückkehrt, bewegt sich ein azyklischer Graph weiterhin in linearer Richtung und kehrt niemals zum Ausgangspunkt zurück. Um mit dem früheren Beispiel des Hühnchen-Reis-Abendessens fortzufahren, können Sie die Grafik nicht vom Kauf des Reises über die Zubereitung des Essens bis zum Kauf des Hühnchens verschieben, da dies eine Rückwärtsbewegung über die Grafik erfordern würde. Es ist unmöglich, das Huhn zuzubereiten, wenn Sie es noch nicht gekauft haben.

DAGs sind probabilistische grafische Darstellungen von Bayes’schen Netzwerken, die darauf abzielen, bedingte Abhängigkeiten zu modellieren (z. B. hängt das Essen davon ab, ob es zuerst zubereitet wird).

Mehrere Kryptowährungen verwenden DAGs anstelle von Blockchain-Datenstrukturen, um Transaktionen zu verarbeiten und zu validieren. Bei Blockchains bauen alle Knoten in einem Netzwerk auf derselben einzigen Blockchain auf, wobei jeder Block auf den vorherigen verweist. Ein möglicher Nachteil dieser Struktur besteht darin, dass der Transaktionsdurchsatz des Netzwerks begrenzt wird, da nur so viele Transaktionen in einen einzelnen Block passen und nur so viele Blöcke in einer bestimmten Zeit validiert werden können. In einem DAG-Netzwerk sind Transaktionen direkt miteinander verknüpft und nicht in Blöcken gruppiert, und Transaktionen können gleichzeitig mit anderen verarbeitet werden. Das Ergebnis ist ein geringerer Engpass beim Transaktionsdurchsatz.