Directed Acyclic Graphs

Graph Theory · Axiom Academy

LESSON Directed Acyclic Graphs (DAGs) Understanding DAGs: fundamental structures for ordering, scheduling, and dependency resolution A directed acyclic graph (DAG) is a directed graph that contains no directed cycles. In other words, there is no way to start at any vertex and follow a sequence of directed edges that eventually loops back to the starting vertex. The animation below shows the difference between a DAG and a directed graph with cycles. A topological ordering (or topological sort) of a DAG is a linear ordering of its vertices such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. This characterization is fundamental: the existence of a topological ordering is equivalent to being acyclic. Every DAG has at least one topological ordering, though it may not be unique. A source is a vertex with in-degree 0 (no incoming edges) A sink is a vertex with out-degree 0 (no outgoing edges) This property is crucial for many DAG algorithms and provides a starting point for topological sorting. 4. DAGs Represent Partial Orders There is a deep connection between DAGs and partial orders. A DAG can be viewed as the Hasse diagram of a partial order where: A directed edge (u, v) means u precedes v in the ordering The transitive closure gives the complete partial order relation DAGs appear throughout computer science and applied mathematics:

This is the written version of the interactive lesson above. See the full Graph Theory course.