Skip to main content

directed acyclic graph

Definition

From Wikipedia (source):

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG /ˈdæɡ/ (listen)) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another.

A directed acyclic graph (DAG)

Why a directed acyclic graph (DAG)

Following directions in a DAG will never form a closed loop. Steps through a DAG are finite. That's the main reason to choose for a DAG.

Unique properties

From Wikipedia (source):

A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions.

Applications

From Wikipedia (source):

DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling).