Definition
A directed acyclic graph (DAG) is a directed graph that contains no directed cycles.
Properties
- Every DAG has at least one vertex with no incoming edges (a source).
- Every DAG has at least one vertex with no outgoing edges (a sink).
- DAGs admit a topological ordering of their vertices.