algorithm - 从边缘构建树

Question

我有边缘，我想用它构建一棵树。

问题是，只有当边按特定顺序时，我才能构建树结构。 订单示例:

(vertex, parent_vertex)

good:              bad:
(0,  ) <-top       (3, 2)
(1, 0)             (1, 0)
(2, 1)             (3, 2)
(3, 2)             (0,  ) <-top

我迭代抛出边，并为当前顶点尝试在创建的树中找到它的父节点，然后构造节点并插入它。

result tree:

0 - 1 - 2 - 3

因此，树中始终必须存在新添加的顶点的父级。 问题是如何对输入边进行排序。声音告诉我有关拓扑排序的信息，但它是针对顶点的。是否可以正确排序？

Answer 1

@mirt 感谢您指出我的方法的优化，您有更好的吗？ 我将把下面的算法作为引用

最初构建一个 HashMap 来存储树中的元素:H，添加根(在您的情况下为空/或代表该根的任何内容)

采用 (_child, _parent)

1. 循环遍历整个列表。 在列表中。 (每对都是元素)
2. 对于每一对，查看 _child 和 _parent 是否存在于 HashMap H 中，如果没有找到，则为缺失的创建树节点并将它们添加到 H 中，并将它们与父子关系链接起来。
3. 迭代结束时您将留下树。

复杂度为 O(n)。