Directed acyclic graph

A directed graph with no directed cycles, so following its arrows can never return to the starting vertex. Its structure admits a topological ordering of vertices.

Directed graph: A graph whose edges have orientations from one vertex to another. A directed acyclic graph is a directed graph with the additional restriction that cycles are absent.
Topological sorting: An ordering of vertices in which every directed edge points from an earlier vertex to a later one. Every directed acyclic graph has such an ordering, which exposes its dependency structure.
Dependency graph: A graph representing which components depend on other components. Acyclic dependencies can be processed in an order that satisfies every prerequisite.
Partially ordered set: A set equipped with a relation that is reflexive, antisymmetric, and transitive. Reachability in a directed acyclic graph induces a partial order on its vertices.
Graph theory: The mathematical study of vertices, edges, and the structures they form. Directed acyclic graphs are a fundamental graph-theoretic structure.
Kahn's algorithm: An algorithm that repeatedly removes vertices with no incoming edges to produce a topological ordering. It detects cycles when vertices remain after no source can be removed.
Build system: Software that determines and performs the steps needed to produce files or programs. Build systems use directed acyclic graphs to schedule prerequisite tasks.
Tournament: A directed graph with exactly one directed edge between every pair of distinct vertices. Every tournament with at least three vertices contains a directed cycle, unlike an acyclic graph.
Directed path: A sequence of vertices joined by edges that all point in the direction of travel. A directed cycle would be a directed path that returns to its starting vertex.
Depth-first search: A graph traversal that explores each path as far as possible before backtracking. A back edge found during depth-first search reveals a directed cycle.

Linked from 17 pages