javascript - 列出开放有限有向图中给定节点的所有可能路径

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

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

我知道的方法要求我有嵌套循环(顺序n^2)，执行此操作的最佳算法是什么。

请注意，上述结构是有向无环图上的 DFS 的结果(如果此信息有任何帮助，即在 dfs 迭代本身期间记录信息)

Answer 1

您可以使用递归方法来构建路径数组，因为您有 {key:2,parent:3} 两次，您可以使用 Set 和 end 来删除重复项。

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)