Statistics How To

Acyclic Graph & Directed Acyclic Graph: Definition, Examples

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 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.

If you prefer an online interactive environment to learn R and statistics, this free R Tutorial by Datacamp is a great way to get started. If you're are somewhat comfortable with R and are interested in going deeper into Statistics, try this Statistics with R track.

Comments are now closed for this post. Need help or want to post a correction? Please post a comment on our Facebook page and I'll do my best to help!
Acyclic Graph & Directed Acyclic Graph: Definition, Examples was last modified: October 12th, 2017 by Andale

One thought on “Acyclic Graph & Directed Acyclic Graph: Definition, Examples