DAG 和树在 Git 中有何不同？

Question

我经常读到Git使用有向无环图（DAG）数据结构，每个提交作为一个节点，分支和标签等东西作为指向节点的指针。

但是当我尝试使用gitk等工具可视化我的提交历史时，它看起来更像一棵树而不是图，因为每个父子关系都是单向的。

那么，有向无环图和树之间有什么区别，特别是与Git相关的区别？

- Jonathan.Brink

Answer 1

但是，当我尝试使用像gitk这样的工具可视化我的提交历史时，它看起来更像一棵树而不是一个图，因为每个父子关系都是单向的。

一个DAG（有向无环图），就像一棵树一样，可以布置成所有父子关系都是单向的。它们之间的区别在于DAG中的节点可以有多个父节点。Git中最常见的情况是进行合并操作。合并提交将拥有所有已合并的提交作为父节点。树不允许节点有多个父节点。

请注意，合并提交C6有两个父节点C4和C5。

(Image source)

- John Kugelman

---

一棵树最多只有一个根节点，而有向无环图可以包含多个根节点，甚至多个不相连的子图。 - jub0bs

@jub0bs 抱歉，我无法想象Git存储库如何有多个根，以及可能存在一个断开的子图。 - Betlista

@Betlista 当然可以。在上面的图中，如果C3没有父节点C2呢？它可能没有父节点。那么它和C0都将成为根节点。此外，如果C6没有C5作为父节点，那么master和iss53将彼此分离，没有共同的提交。 - John Kugelman

我所使用的大多数 Git 存储库只有一个根提交。虽然在技术上可以创建多个根提交，并且在某些情况下这可能很有用，但在日常开发工作中不会意外发生。 - jbyler