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是否存在于hash map H中，如果没有，则为缺失的创建树节点并将它们添加到H中，并将它们与父子关系链接起来。
3. 您将在迭代结束时留下树。

复杂度为 O(n)。