Алгоритм поиска дерева в 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]
};

Имя узла - это число, а значения - это отношения (имя следующего узла):

Я хочу go от 0 до 9, я мог go следующими способами:

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

также 0 -> 2 -> 7 -> 6 -> 9

также 0 -> 2 -> 7 -> 4 -> 6 -> 9

Базовые c правила:

• Все маршруты односторонние (например: 2 может go до 3, но не наоборот) (не может go 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; }