分類中兩個概念的最低上位

Question

如何以有效的方式找到兩個概念的最低上位？ 分類中兩個概念的最低上位意味着兩個概念中最具體的共同祖先。例如，在下面的分類圖中，如何找到感覺1和感覺2的最常見的祖先？

BTW，我發現多義的羅伯託的Navigli的調查這個問題。他沒有提及如何計算上級。

Answer 1

您可以沿着Sense 1一側的層次結構上升，並將所有這些節點標記爲Sense 1的祖先。然後去Sense 2一側，並檢查每個祖先，看看你是否標記爲Sense 1的祖先。你發現的第一個將是最低的上位或最具體的共同祖先。

在你的圖片中，無論你從哪個感覺開始，它都是根節點。

Answer 2

http://en.wikipedia.org/wiki/Lowest_common_ancestor包含指針，用於在通常情況下我們有一棵樹時最不共同的祖先問題的更高效的算法，所以每個節點都有一個父節點，除了根節點沒有父節點。這些算法可以在樹的線性時間預處理之後以恆定的時間回答查詢。

我不知道這些算法是否會推廣到您可以有多個父項的情況。看起來明顯的概括將相當於刪除樹中的鏈接，以確保在仍連接的情況下，每個節點至多隻有一個父節點。