Statistics How To

Acyclic Graph & Directed Acyclic Graph: Definition, Examples

Share on

Descriptive Statistics > Directed Acyclic Graph

A tree with nodes A B C D E  F and G.

A tree with nodes A B C D E F and G.

Directed acyclic graphs (DAGs) are used to model probabilities, connectivity, and causality. A “graph” in this sense means a structure made from nodes and edges.

  • Nodes are usually denoted by circles or ovals (although technically they can be any shape of your choosing).
  • Edges are the connections between the nodes. An edge connects two nodes. They are usually represented by lines, or lines with arrows.

DAGs are based on basic acyclic graphs.

What is an Acyclic Graph?

An acyclic graph is a graph without cycles (a cycle is a complete circuit). When following the graph from node to node, you will never visit the same node twice.

minimum spanning tree

This graph (the thick black line) is acyclic, as it has no cycles (complete circuits).

A connected acyclic graph, like the one above, is called a tree. If one or more of the tree “branches” is disconnected, the acyclic graph is a called a forest.
This graph has a complete circuit and so is not acyclic.

This graph has a complete circuit and so is not acyclic.

What is a Directed Acyclic Graph?

A directed acyclic graph is an acyclic graph that has a direction as well as a lack of cycles.
directed acyclic graph

The parts of the above graph are:

  • Integer = the set for the Vertices.
  • Vertices set = {1,2,3,4,5,6,7}.
  • Edge set = {(1,2), (1,3), (2,4), (2,5), (3,6), (4,7), (5,7), (6,7)}.

A directed acyclic graph has a topological ordering. This means that the nodes are ordered so that the starting node has a lower value than the ending node. A DAG has a unique topological ordering if it has a directed path containing all the nodes; in this case the ordering is the same as the order in which the nodes appear in the path.

In computer science, DAGs are also called wait-for-graphs. When a DAG is used to detect a deadlock, it illustrates that a resources has to wait for another process to continue.

Stephanie Glen. "Acyclic Graph & Directed Acyclic Graph: Definition, Examples" From Elementary Statistics for the rest of us!

Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!

Comments? Need to post a correction? Please post a comment on our Facebook page.