最低公共祖先算法有哪些实际应用？

Question

6

我正在查看这个问题，然后阅读有关Tarjan的离线最近公共祖先算法的内容。我以前从未接触过LCA算法的任何应用。

LCA算法通常在哪些地方使用？

- Lazer

1

科学计算中的空间数据结构树，计算生物学中的字符串后缀树等等。抱歉忘记了具体细节，但肯定很有用。 - polygenelubricants

3个回答

5

不知道它在哪里被使用，但我有几个想法可能会用到：

- Jens Schauder

1

版本控制 -> 三方合并: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge - Lazer

当寻找不同后缀的词根时，它对某些字符串处理也非常有用。 - Arnold Spence

-1

我刚刚写了一篇关于如何在元基因组的环境下实现一个（具有任意长度节点的）分类树问题的自己的算法的博客文章：

祝好,

Pablo

- ppareja

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Doug Currie · Accepted Answer

在编译器中，两个基本块的最近公共祖先是可以放置计算以使其对两个块都可用的位置。这可能对消除常见子表达式或插入phi节点进行SSA转换很有用。这些算法已经发展成熟且高度优化，因此LCA本身可能难以观察，例如SSA和PRE。