Menu
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?
611
Tree is a special kind of graph that has no cycle so that is known as DAG (Directed Acyclic Graph). Tree is a hierarchical model. In graph, each node has one or more predecessor nodes and successor nodes. The graph is traversed by using Depth First Search (DFS) and Breadth First Search (BFS) algorithms.
The history in Git is formed from the commit objects; as development advances, branches are created and merged, and the history will create a directed acyclic graph, the DAG, because of the way that Git ties a commit to its parent commit. The DAG makes it easy to see the development of a project based on the commits.
Commit graphsGit chooses directed acyclic graph (DAG) as commit tree pattern.
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.
(Image source)
Notice how the merge commit C6 has two parents, C4 and C5.
148
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
