计算机科学

首页 > 计算机科学

最近公共祖先 (图论)

2018-08-30 10:00:50     所属分类:离散数学

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

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


上一篇:离散数学
相关推荐