输入是一个数组 数组元素数据结构是 { 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
拓扑排序吧,遍历输入用邻接表存图,同时记录节点度。
|