最低公共祖先算法的實際應用是什麼？

Question

我正在看this question，然後閱讀約Tarjan's least common ancestors algorithm。我以前從未遇到LCA算法的任何應用。

這樣的LCA算法常用於哪裏？

Answer 1

不知道它在哪裏使用，但我有幾個想法在那裏它可能會使用：

• 計算機圖形學：經常3D景觀得到分成形成一個樹狀結構的多維數據集。如果您有一個包含在兩個此類立方體中的對象，則LCA算法會爲您提供包含較大立方體的最小對象。爲了找到物種及其最低的共同祖先之間的關係氏族

• 分析

• 版本控制系統的合併算法

Answer 2

在編譯器中，兩個基本塊的LCA是您可以放置​​一個計算器，以便它們都可用。這可能有助於消除常見的子表達式，或插入用於SSA轉換的phi節點。這些算法以及進化和高度優化的，雖然如此，在LCA本身可能很難看到，例如，SSA和PRE

Answer 3

我剛寫了一篇我是如何實現我自己的算法了這個問題的博客文章（擴展在宏基因組學的上下文中一組具有任意長度的分類法樹的節點）的：

http://blog.bio4j.com/2012/02/finding-the-lowest-common-ancestor-of-a-set-of-ncbi-taxonomy-nodes-with-bio4j/

乾杯，

巴勃羅