3

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

具体来说，我认为我想要的是

  • 我们有一些H具有“最低共同祖先”功能的类型lca。这给出H了树状结构。

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

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

  • t应该满足性质

    • 全部s在S标签的某个节点中t

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

    • h标签的任何元素H不超过一个节点t

    • 如果h1标签n1和h2标签n2则标记和inlca(h1, h2)的最低共同祖先。n1n2t

我的问题是：“这是已知算法的已知问题吗？”。我怀疑是这样。它似乎与拓扑排序非常相似。我有一个基于合并排序的算法的想法，但如果已知算法已经存在，那么没有理由想出我自己的算法。

4

1 回答 1

1

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

这个主题让我想起了 cladistics 算法， http://bio.slu.edu/mayden/systematics/bsc420520lect12.html。然而，这些都更容易和更难。更容易，因为通过检查很容易判断哪些表格接近另一个。更难，因为挑战在于您不了解LCA。所以追求这可能是一个有趣的支线，但可能不是很有帮助。

于 2017-11-10T19:05:07.290 回答