algorithm - 最低共同祖先算法的实际应用是什么？

Question

我正在查看这个问题，然后阅读有关Tarjan 的最不常见的祖先算法。我以前从未遇到过 LCA 算法的任何应用。

这样的 LCA 算法常用在哪里？

Answer 1

在编译器中，两个基本块的 LCA 是您可以放置​​计算的地方，因此两者都可以使用。这对于消除常见的子表达式或插入 phi 节点以进行 SSA 转换可能很有用。但是，这些算法经过了很好的改进和高度优化，因此 LCA 本身可能很难看到，例如SSA和PRE

Answer 2

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

• 计算机图形学：通常 3D 场景被分割成立方体，形成树状结构。如果您有一个包含在两个这样的立方体中的对象，则 LCA 算法会为您提供最小的包含较大的立方体。

• 分析氏族以发现物种与其最低共同祖先之间的关系

• 版本控制系统的合并算法

Answer 3

我刚刚写了一篇博客文章，介绍了如何在宏基因组学的背景下为分类树实现我自己的算法（扩展到一组任意长度的节点）：

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

干杯，

巴勃罗