# Acyclic Graph & Directed Acyclic Graph: Definition, Examples

Descriptive Statistics > Directed Acyclic Graph

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.

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.

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

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.

------------------------------------------------------------------------------

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. If you rather get 1:1 study help, Chegg Tutors offers 30 minutes of free tutoring to new users, so you can try them out before committing to a subscription.

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.