javascript - Javascript中的搜索树算法，存储了所有可能的路线？

Question

我以为这是一棵树，但我完全不确定。我有下一个数据结构:

const routes = {
  0: [1, 2, 3],
  1: [8, 6, 4],
  2: [7, 8, 3],
  3: [8, 1],
  4: [6],
  5: [8, 7],
  6: [9, 4],
  7: [4, 6],
  8: [1],
  9: [1, 4]
};

节点名称是一个数字，值是关系(下一个节点名称):
我想从 0 到 9，我可以通过以下方式:

0 -> 1 -> 4 ->6 -> 9

还有 0 -> 2 -> 7 -> 6 -> 9还有 0 -> 2 -> 7 -> 4 -> 6 -> 9基本规则:

所有路线都是一种方式(例如:2 可以转到 3，但反之不行)
(不能去0 -> 2 ->7 -> 4 -> 6 -> 4 <<< nope)

我试过这个:

function finder(origin, target, collection, traker) {
  const relations = collection[origin];
  console.log("ORIGIN: ", origin);
  console.log("TARGET: ", target);
  console.log("RELATIONS: ", collection[origin]);

  if (itsMe(origin, target)) {
    console.log("ARE YOU LOOKIN TO YOU ?");
    return { trak: traker, success: true };
  }

  if (heKnowsTarget(target, relations)) {
    console.log("YAY HE KNOWS WHO I WANT TO MEET");
    return { trak: traker, success: true };
  }

  const relationsToSearch = removeMyself(origin, relations);
  console.log("RELATIONS TO SEARCH WITHOUT ME: ", relationsToSearch);

  traker.push(origin);
  console.log("TKRACER", traker);
  const filteredSear = removeParenTrackers(traker, relationsToSearch);

  console.log("RELATIONS WITHOUT TRAKING: ", filteredSear);

  for (let i = 0; i < relationsToSearch.length; i++) {
     // at this point every starts to be destructive so remove this part
  }
}

我不知道如何调用它，或者如何保留所有跟踪数据并返回上一个以存储和分析结果。
有人可以帮忙吗？

Answer 1

您可以访问所有节点并省略已经访问过的节点。
递归方法:

function getRoutes(routes, start, end) {
    function go(node, visited = []) {
        visited.push(node);
        if (node === end) {
            result.push(visited);
            return;
        }
        
        routes[node].forEach(n => {
            if (visited.includes(n)) return;
            go(n, [...visited]);
        });
    }

    var result = [];
    go(start);
    return result;
}

const routes = { 0: [1, 2, 3], 1: [8, 6, 4], 2: [7, 8, 3], 3: [8, 1], 4: [6], 5: [8, 7], 6: [9, 4], 7: [4, 6], 8: [1], 9: [1, 4] };

getRoutes(routes, 0, 9).forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

使用堆栈的迭代方法:

function getRoutes(routes, start, end) {
    var stack = [[start, []]],
        result = [];

    while (stack.length) {
        const [node, visited] = stack.shift();
        visited.push(node);
        if (node === end) {
            result.push(visited);
            continue;
        }
        for (const n of routes[node]) {
            if (visited.includes(n)) continue;
            stack.push([n, [...visited]]);
        }
    }

    return result;
}

const routes = { 0: [1, 2, 3], 1: [8, 6, 4], 2: [7, 8, 3], 3: [8, 1], 4: [6], 5: [8, 7], 6: [9, 4], 7: [4, 6], 8: [1], 9: [1, 4] };

getRoutes(routes, 0, 9).forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }