CODEWITHSUNDEEP
gitdata-structures
Jonathan.Brink
Jonathan.Brink

Reputation: 25433

DAG vs. tree using Git?

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?

Upvotes: 70

Views: 23820

Answers (1)

John Kugelman
John Kugelman

Reputation: 362037

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.

Upvotes: 93

Related Questions