DAGs

A directed acyclic graph, or DAG, is a directed graph with no directed cycles. It consists of a set of vertices and a set of edges with direction, such that no sequence of edges v1→v2→...→vk→v1 exists.

A central concept is topological ordering, a linear ordering of vertices in which every edge u→v goes from an earlier to a later vertex. A directed graph is a DAG if and only if a topological ordering exists.

Nodes have in-degrees and out-degrees. A vertex with in-degree zero is a source, and one with out-degree zero is a sink. Acyclicity ensures that these notions can be used to process the graph in a forward pass.

Algorithms for DAGs include topological sort, such as Kahn's algorithm or a DFS-based approach, which run in O(V+E) time. In DAGs, the longest path problem can be solved in linear time by processing vertices in topological order with dynamic programming. Reachability queries can also be resolved efficiently using traversal in the sorted order.

Representation and structure: DAGs can be stored as adjacency lists or adjacency matrices; subgraphs of DAGs are DAGs themselves. They often represent partial orders and dependency relations.

Applications: Build systems and task scheduling rely on DAGs to express prerequisites. Data processing pipelines and workflow orchestration systems define tasks and dependencies as DAGs. Git’s commit history is a DAG because commits point to predecessors and cycles cannot form. Limitations and variants: the presence of a cycle means the graph is not a DAG. DAGs are a restricted model that enables efficient algorithms for dependency analysis and scheduling.