如何找到简单结构之间的所有可能路径？

Question

我有这样的结构：

[
  {index: 1, children: [2]},
  {index: 2, children: [3, 4]}
  {index: 3, children: [4]}
  {index: 4, children: []}
]

我想在这个结构中找到所有可能的路径，所以我最终得到最长的路径（我需要决定整个行程的最大长度）。所以在这个结构中，算法应该导出类似

的东西

[[1, 2, 3, 4], [1, 2, 4]]

或者只是最终答案，即 4（最长行程的长度）。我在网上找到了一些解决方案，此时我确信这只能通过递归解决，但就是想不通。任何实现这个的想法都会很棒，我正在尝试用 js 解决这个问题。

Answer 1

let input = [{ index: 1, children: [2] }, { index: 2, children: [3, 4] }, { index: 3, children: [4] }, { index: 4, children: [] }];

function find_all_possible_paths(nodes, key) {
  let result = [];
  function next(key, paths = [key]) {
    let node = nodes.find(v => v.index == key);

    if (node?.children.length)
      for (let index of node.children) {
        if (paths.includes(index)) throw new Error("Reference cycle error:\n" + JSON.stringify({ paths, node }, null, 4));
        next(index, paths.concat(index))
      }
    else result.push(paths)
  }
  next(key);
  return result
}

console.log(find_all_possible_paths(input, 1))

如何找到简单结构之间的所有可能路径？

How do I find all possible paths between a simple structure?

arrays

children

structure

path

nodes