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

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 并结束以删除重复项。

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)

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

List all possible paths from a given node in open Finite Directed Graph

javascript

arrays

depth-first-search