68

I've often read that Git uses the directed acyclic graph (DAG) data structure, with each commit as a node, and things like branches and tags as pointers to nodes.

But when I try to visualize my commit history using tools like gitk, it looks more like a tree than a graph since every parent-child relationship is directed one way.

So, what's the difference between a DAG and a tree, specifically with regards to Git?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Jonathan.Brink
  • 23,757
  • 20
  • 73
  • 115

1 Answers1

88

But when I try to visualize my commit history using tools like gitk, it looks more like a tree than a graph since every parent-child relationship is directed one way.

A DAG, like a tree, can be laid out such that all parent-child relationships are one-way. The difference between them is that nodes in a DAG can have multiple parents. The most common case of this in Git is when you do a merge. A merge commit will have all of the commits that were merged as parents. A tree doesn't allow nodes to have multiple parents.

Graph with merging (Image source)

Notice how the merge commit C6 has two parents, C4 and C5.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
  • 14
    @Jonathan.Brink Also, a tree can have at most only one root, whereas a DAG can contain several roots, and even multiple disconnected subgraphs. – jub0bs Oct 16 '14 at 12:58
  • 1
    @jub0bs Sorry, but I cannot imagine how Git repository can have several roots as well as how there could be a disconnected subgraph – Betlista Jan 12 '20 at 11:03
  • 2
    @Betlista It certainly can. In the graph above, what if C3 did not have C2 had no parent? It could have no parent. Then both it and C0 would be roots. Furthermore, if C6 did not have C5 as a parent then `master` and `iss53` would be disconnected from each other with no common commits. – John Kugelman Jan 12 '20 at 15:09
  • Most git repositories that I've worked with only have a single root commit. Although it's technically possible to create multiple root commits, and there are circumstances when this can be useful, it won't happen by accident in your day-to-day dev work. – jbyler Mar 01 '23 at 18:13