Home > Directed acyclic graph

Every directed acyclic graph has a topological sort, an ordering of the vertices such that each vertex comes before all vertices it has edges to.

DAGs can be considered to be a generalization of trees in which certain subtrees can be shared by different parts of the tree. In a tree with many identical subtrees, this can lead to a drastic decrease in space requirements to store the structure. Conversely, a DAG can be expanded to a forest of rooted trees using this simple algorithm:

• While there is a vertex v with in-degree n > 1,
  • Make n copies of v, each with the same outgoing edges but no incoming edges.
  • Attach one of the incoming edges of v to each vertex.
  • Delete v.

If we explore the graph without modifying it or comparing nodes for equality, this forest will appear identical to the original DAG.

Some algorithms become simpler when used on DAGs instead of general graphs. For example, search algorithms like depth-first search normally must mark vertices they have already visited and not visit them again. If they fail to do this, they may never terminate because they follow a cycle of edges forever. Such cycles do not exist in DAGs.

Directed acyclic graphs have many important applications in computer science, including:

• The directory structure in a typical UNIX directory filesystem
• The parse tree constructed by a compiler
• Bayesian networks
• A reference graph that can be garbage collected using simple reference counting
• The reference graph of every purely functional data structure
• Dependency graphs such as those used in instruction scheduling and makefiles