{title2=Directed Acyclic Graph}

Every <tree (data structure)> is a <directed acyclic graph>.

But not every <directed acyclic graph> is a tree.

Example of a tree (and therefore also a DAG):
``
5
|
4 7
| |
3 6
|/
2
|
1
``
Convention in this presentation: arrows implicitly point up, just like in a `git log`, i.e.:
* 1 is parent of 2
* 2 is parent of 3 and 6
* 3 is parent of 4
and so on.

Example of a DAG that is not a tree:
``
7
|\
4 6
| |
3 5
|/
2
|
1
``
This is not a tree because there are two ways to reach 7:
* 2, 3, 4, 7
* 2, 5, 6, 7

But we often say "tree" intead of "DAG" in the context of Git because DAG sounds ugly.

Example of a graph that is not a DAG:
``
6
^
|
3->4
^  |
|  v
2<-5
^
|
1
``
This one is not acyclic because there is a cycle 2, 3, 4, 5, 2.


Ciro Santilli @cirosantilli 37

 Incoming links: Directed acyclic graph