从最近公共祖先重构树的算法名称是什么？

Question

我想编写一个工具，处理一些树形结构的数据。（实际上，它将在Git修订DAG的类似树状子集上工作，但这对于此问题并不重要）。特别是，我想要一种算法，用于重建一个输入集中所有“连接点”组成的子树。

具体而言，我认为我需要：

• 我们有一些类型为H的对象，它具有“最近公共祖先”函数，在其中运行lca。这使得H具有类似树形的结构。

• 算法以H的某个子集S作为输入。

• 输出应该是一个多叉树t，其节点由H的值标记。

• t应满足以下属性：

  • S中的所有元素都标记了t的某个节点。

  • t的叶子节点只能由S的元素标记。

  • 对于H的任何元素h，其标记的节点不超过一个。

  • 如果h1标记为n1，h2标记为n2，则lca（h1，h2）标记为t中n1和n2的最近公共祖先。

我的问题是：“这是一个已知的问题吗？是否有已知的算法？”我认为它与拓扑排序非常相似。我有一个基于归并排序的算法想法，但如果已经存在已知的算法，那就没必要自己发明了。

- Tom Ellis

---

从“最近公共祖先”的角度来看，树的根节点是否是所有非根节点的“祖先”？我认为您描述的结构也被称为半格。我认为所需的输出将被称为输入的“半格壳”。 - Codor

是的，这个结构是半格。"半格壳"是一个很好的命名！ - Tom Ellis

如果你能告诉我_semilattical_是否是一个真正的单词，那你真的会救我的一天。 - Codor

Answer 1

我不知道你叫它什么，但我会先比较所有元素对以构建树的部分顺序，然后进行拓扑排序，最后从中构建树。(排序的目的是现在您知道第一个元素是根，每个元素依次都将成为叶子。)

这个主题让我想起了分类算法http://bio.slu.edu/mayden/systematics/bsc420520lect12.html。然而，这两者既容易又困难。容易是因为通过检查可以很容易地判断哪些形式与另一个相似。更难的是挑战是您不知道LCA。因此，追求这一点可能是一个有趣的副线，但可能没有太大帮助。

- btilly

---

这是一个很好的简单算法。我最初希望有一个O(n log n)的算法，但我怀疑在少于O(n^2)的操作中无法确定图是否完全断开连接。 - Tom Ellis

我不理解最近公共祖先函数的评估如何生成拓扑排序；请澄清。 - Codor

@Codor 如果 lca(a, b) = a，则 a < b 定义了一个偏序关系。这就是拓扑排序所需的全部内容。 - btilly