最近公共祖先 (圖論)

此條目頁的主題是圖論和計算機科學中的概念。關於生物學中的最近公共祖先，請見「最近共同祖先 (生物)」。

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

在本圖中，x與y的最近公共祖先被標記為深綠色，其他公共祖先被標記為淺綠色

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