algorithm - 从最低共同祖先重建树的算法名称？

Question

我想编写一个适用于某些树结构数据的工具。 (事实上​​ ，它将在 git 修订版 DAG 的树状子集上工作，但这对于这个问题并不重要)。特别是我想要一种算法来重建由给定输入集的所有“连接点”组成的树的子集。

具体我想我想要的是

• 我们有一些类型H，它有一个“最低共同祖先”函数，lca。这为 H 提供了树状结构。

• 该算法将 H 的一些子集 S 作为输入。

• 输出应该是一个多路树 t，其节点标记为 H。

• t应满足性质

  • S中的所有s标记了t

    的某个节点

  • t的叶子只能被S的元素标记

  • H 的任何元素 h 标签不超过 t

    的一个节点

  • 如果 h1 标记为 n1 并且 h2 标记为 n2 那么 lca(h1, h2)标记t中n1和n2的最低共同祖先。

我的问题是:“这是已知算法的已知问题吗？”。我怀疑是的。它看起来非常类似于拓扑排序。我有一个基于合并排序的算法的想法，但如果已知算法已经存在，就没有理由提出我自己的算法。

Answer 1

我不知道你怎么调用它，但我会首先比较所有元素对以构建树的偏序，然后进行拓扑排序，然后从中构建树。 (排序的重点是现在你知道第一个元素是根，每个元素依次是叶子。)

这个主题让我想起了分支算法，http://bio.slu.edu/mayden/systematics/bsc420520lect12.html .但是，这些既容易又难。更容易，因为通过检查很容易分辨出哪些表格与另一个表格接近。更难，因为挑战在于您不了解 LCA。所以追求它可能是一个有趣的旁路，但可能不是很有帮助。