Incoming links: Directed acyclic graph
Every tree is a directed acyclic graph.
But not every directed acyclic graph is a tree.
Example of a tree (and therefore also a DAG):Convention in this presentation: arrows implicitly point up, just like in a and so on.
5
|
4 7
| |
3 6
|/
2
|
1git log, i.e.:- 1 is parent of 2
- 2 is parent of 3 and 6
- 3 is parent of 4
Example of a DAG that is not a tree:This is not a tree because there are two ways to reach 7:
7
|\
4 6
| |
3 5
|/
2
|
1- 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:This one is not acyclic because there is a cycle 2, 3, 4, 5, 2.
6
^
|
3->4
^ |
| v
2<-5
^
|
1