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:
- Nodes: A place to store the data.
- Directed Edges: Arrows that point in one direction (the thing that makes this data structure different)
- 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. )
- Leaves: Nodes with no children