名单给定节点在有限开放所有可能的路径有向图

Question

我有一个对象集合是这样的：

[ 
{key:8, parent:'none'}, 
{key:5, parent:8}, 
{key:3, parent:5}, 
{key:2, parent:3}, 
{key:4, parent:5}, 
{key:1, parent:4}, 
{key:3, parent:4}, 
{key:2, parent:3}, 
] 

所有可能的路径：

8->5->3->2 
8->5->4->1 
8->5->4->3->2 

什么将是最简单的方法产生尽可能多的字符串。可能的路径，每个字符串的值是路径序列？

我知道的方式要求我有嵌套循环（order n^2），那么最佳算法是什么？

请注意，上述结构是有向无环图的DFS的结果

Answer 1

您可以将用户递归方法建立的数组（如果该信息以任何方式即DFS迭代过程本身可以帮助记录信息）路径，也因为你有{key:2, parent:3}两次，你可以使用Set并结束删除重复。

var data = [{key:8, parent:'none'},{key:5, parent:8},{key:3, parent:5},{key:2, parent:3},{key:4, parent:5},{key:1, parent:4},{key:3, parent:4}, {key:2, parent:3}] 
 

 
var result = [] 
 

 
function buildStrings(arr, parent, c) { 
 
    return arr.reduce(function(r, e) { 
 
    if (e.parent == parent) { 
 
     var children = buildStrings(arr, e.key, c + e.key + '->') 
 
     if (!children.length) result.push(c + e.key) 
 
     r.push(e) 
 
    } 
 
    return r; 
 
    }, []) 
 
} 
 

 
buildStrings(data, 'none', '') 
 
result = [...new Set(result)] 
 

 
console.log(result)