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

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))