这是一个创建于 2911 天前的主题，其中的信息可能已经有所发展或是发生改变。
输入是一个数组 数组元素数据结构是 { name: string, parent: string } name 是元素名 parent 是父节点名(可以为空)
输出是对输入排序后的数组 排序规则为先把 parent 为空的元素前置，后置元素 parent 值肯定在前置元素中可以找到
算法结果不仅要排序而且要找到 parent 对应错误的元素 而且侦查的到输入是否产生循环依赖
我大概的思路是先生成一个多叉树再用前序遍历出来，但是现在找不出有效的方法根据数组生成多叉树
 |
1
Umix 2016-12-06 11:16:19 +08:00
先把 parent 为空的都找出来，作为 root node ，然后挨个看。比如第一个 root node 的 name 是 a ，那么遍历找一下有没有 parent 为 a 的，先发现了一个 d 后来发现一个 e ，那么按顺序插到 a 的后面，然后挨个遍历 d 和 e 的子节点继续插在后面，这么看发现也就是一个多叉树了。。。做完之后剩下的就是产生循环依赖的元素。。所以如果没理解错的话，是算法实现上卡住了？
|
 |
2
GtDzx 2016-12-06 11:19:49 +08:00
拓扑排序？
|
 |
3
ddhwen 2016-12-06 11:49:25 +08:00 via Android
拓扑排序吧，遍历输入用邻接表存图，同时记录节点度。
|
Select Language