A DAG is a graph that flows in one direction, where no element can be a child of itself. So most of us are familiar with Linked Lists, trees, and even graphs. A DAG is very similar to the first two, and an implementation of the third.


At the very minimum, a DAG will have 4 things:

  1. Nodes: A place to store the data.
  2. Directed Edges: Arrows that point in one direction (the thing that makes this data structure different)
  3. Some great ancestral node with no parents. (Fun fact: Most ancestry trees are actually DAGs and not actually trees because cousins at some point get married to each other. )
  4. Leaves: Nodes with no children