最近公共祖先 (图论)

此条目的主題是图论和计算机科学中的概念。关于生物学中的最近公共祖先，請見「最近共同祖先 (生物)」。

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

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

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