最近公共祖先 (图论)

在图论和计算机科学中，最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有 $v$ 和 $w$ 作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果 $v$ 是 $w$ 的后代，那么 $w$ 就是 $v$ 和 $w$ 的最近公共祖先。

在本图中，x与y的最近公共祖先被标记为深绿色，其他公共祖先被标记为浅绿色

最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。