Search tree algorithm in Javascript with all posible routes stored?

Question

I supposed this is a tree, but i am not sure at all. I have the next data structure:

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]
};

The node name is a number, and the values are the relations (next node name):

I want to go from 0 to 9, I could go by the next ways:

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

also 0 -> 2 -> 7 -> 6 -> 9

also 0 -> 2 -> 7 -> 4 -> 6 -> 9

The basic rules:

All routes are in one way (eg: 2 can go to 3, but not vice versa) (can not go 0 -> 2 ->7 -> 4 -> 6 -> 4 <<< nope)

I tried this:

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

I don't know how to call this, or how to keep all tracking data and return to previous one to store and analyze results after.

Somebody could help?

user_1447675 · Answer

You could visit all nodes and omit nodes who are already visited.

Recursive approach:

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; }

Iterative approach with a stack:

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; }

Search tree algorithm in Javascript with all posible routes stored?

1 Answers