跳至內容

最近公共祖先 (圖論)

維基百科,自由的百科全書
在本圖中,x與y的最近公共祖先被標記為深綠色,其他公共祖先被標記為淺綠色

圖論計算機科學中,最近公共祖先(英語:lowest common ancestor)是指在一個或者有向無環圖中同時擁有vw作為後代的最深的節點。在這裡,我們定義一個節點也是其自己的後代,因此如果vw的後代,那麼w就是vw的最近公共祖先。

最近公共祖先是兩個節點所有公共祖先中離根節點最遠的,計算最近公共祖先和根節點的長度往往是有用的。比如為了計算樹中兩個節點vw之間的距離,可以使用以下方法:分別計算由v到根節點和w到根節點的距離,兩者之和減去最近公共祖先到根節點的距離的兩倍即可得到vw的距離。