最近公共祖先 (图论)

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.