Javascript: 通过对象树构建可能的路径

Question

我有一个对象： {1:[2,3], 2:[3,3], 3:[4,8], 4:[8,8], 8:["End", "End"]} 我想 loop/traverse 通过。

此对象的每个键就像一个点或位置（例如位置 1 或位置 2）。
并且每个位置都链接到一个或两个其他位置，允许您从一个位置跳到另一个位置。这些“链接”由每个键的数组-属性定义。例如，我可以从 location 1 跳到 location 2，或者从 location 3 跳到 location 8。

现在我想以二维数组的形式绘制这些链接。二维数组应包含所有可能的路径，每条路径以 location 1 开头并以 location End 结尾（仅在键 8 的数组中定义）。

到目前为止我有以下代码：

let paths_list;
function find_paths(obk, data={}) {
    paths_list = data?.paths_list || [];
    let newest_path = data?.newest_path || [1];
    let current_number = data?.current_number || 1;
    let next_possible_numbers_iteration = (data.next_possible_numbers_iteration || 0);

    if((current_number == "End" || current_number == undefined) && next_possible_numbers_iteration >= obk[1].length) {
        return paths_list;
    }

    let next_possible_numbers;
    let next_number;

    for(let i = 0; i < 2; i++) {
        if(current_number == "End" || current_number == undefined) {
            next_possible_numbers_iteration++;
            current_number = 1;
            paths_list.push(newest_path);
            newest_path = [1];
        }
        next_possible_numbers = obk[current_number]; // [2,2]
        next_number = next_possible_numbers[next_possible_numbers_iteration];
        newest_path.push(next_number);
        current_number = next_number;
    }
    

    if(current_number != "End" && current_number != undefined) {
        find_paths(obk, {
            paths_list,
            newest_path,
            current_number,
            next_possible_numbers_iteration
        });
    } else {
        next_possible_numbers_iteration++;
        paths_list.push(newest_path);
        find_paths(obk, {
            paths_list,
            current_number,
            next_possible_numbers_iteration
        });
    }
}


let my_obk = {1:[2,3], 2:[3,3], 3:[4,8], 4:[8,8], 8:["End", "End"]};
find_paths(my_obk);
console.log(paths_list);

问题

但是有一个轻微的问题：函数 returns 只是一些可能的路径。具体来说，return 正确的是：

1,2,3,4,8,结束
1,3,8,结束

但 return 其他路径不会，例如：

1,2,3,8,结束

这是因为该函数只在每个数组中的相同位置搜索-属性，并且不会改变它搜索的位置（由next_possible_numbers_iteration定义）。

简而言之，我的问题是如何让函数查看每个数组（或属性）中的不同位置，而不是只查看所有数组中的一个。这在您阅读时可能没有任何意义，但如果您查看变量 next_possible_numbers_iteration 的使用方式，您就会明白我的意思。实在不行就改我的功能吧

Answer 1

您可以采用递归方法并从给定节点收集所有路径。

此方法仅采用数组中的唯一目标。

递归函数通常包含一个退出条件，在该条件下函数决定再次调用该函数或只为该函数保留一个值。这也发生在这里。

如果找到作为目标的节点，则它 returns 具有单个值的嵌套数组，即目标节点。

要理解该算法，请使用一个简单的三节点对象，例如

{ 1: [2, 3], 2: ['End'], 3: ['End'] }

最终结果将是两条路径：

[
    [1, 2, 'End'],
    [1, 3, 'End']
]

该算法适用于 breadth-first search，因为递归和查找结束。

这意味着它 returns 用于 getPathes('End', 'End')

的最终调用

[['End']]

对于 getPathes(2, 'End') 的上一次调用，它 returns

[[2, 'End']]

模拟 getPathes(3, 'End') 它 returns

[[3, 'End']]

两个数组都在 getPathes(1, 'End') 的调用内部返回，其中实际节点被添加到嵌套调用的所有数组之前。

const 
    getPathes = (from, to) => {
        if (from === to) return [[to]];
        return nodes[from].flatMap(n => getPathes(n, to).map(p => [from, ...p]));
    },
    nodes = { 1: [2, 3], 2: [3], 3: [4, 8], 4: [8], 8: ["End"] },
    pathes = getPathes(1, 'End');

pathes.forEach(p => console.log(...p));

Answer 2

@Nina 的递归解决方案看起来很棒

如果你想要一个迭代的方法来解决同样的问题，你可以检查这个

继续创建新路径，直到所有路径结束:)

const obj = { 1: [2, 3], 2: [3, 3], 3: [4, 8], 4: [8, 8], 8: ['End', 'End'] };

let paths = obj[1].map((x) => [1, x]);
let complete = false;

while (!complete) {
  complete = true;
  
  const result = [];
  paths.forEach((path) => {
    const lastElementOfPath = path[path.length - 1];
    const nextPathDirections = obj[lastElementOfPath];
    if (nextPathDirections) {
      Array.from(new Set(nextPathDirections)).forEach((nextPathElement) => {
        result.push([...path, nextPathElement]);
        if (nextPathElement !== 'End' && !!obj[nextPathElement]) {
          complete = false;
        }
      });
    } else {
      result.push([...path]);
    }
  });
  
  paths = result;
}


// Paths will be your desired result
paths.forEach(path => console.log(...path))

Javascript: 通过对象树构建可能的路径

Javascript: build possible paths through an object tree

javascript

arrays

tree

logic

object

问题