How to keep track of path in BFS Graph search JavaScript

user_13858175 0
Viewed 858

I am working on BFS algorithms and I'm having a hard time figuring out how to keep track of the shortest path.
Below the code I've used :

const graph = {
  1: [2, 3, 4],
  2: [5, 6],
  3: [10],
  4: [7, 8],
  5: [9, 10],
  7: [11, 12],
  11: [13],
};

function bfs(graph, start, end) {
  let queue = [...graph[start]];
  let path = [start];
  let searched = [];
  while (queue.length > 0) {
    let curVert = queue.shift();
    if (curVert === end) {
      return path;
    } else if (searched.indexOf(curVert) === -1 && graph[curVert]) {
      queue = [...queue, ...graph[curVert]];
      searched.push(curVert);
      path.push(curVert);
    }
  }
}

console.log(bfs(graph, 1, 13));

what I would to get in return of the function call is the shortest path. In this case [1, 4, 7, 11, 13].

shortest-path ecmascript-6 breadth-first-search algorithm javascript
2 Answers

You need to store the path for each visited node as well.

const graph = { 1: [2, 3, 4], 2: [5, 6], 3: [10], 4: [7, 8], 5: [9, 10], 7: [11, 12], 11: [13] };

function bfs(graph, start, end) {
    let queue = [[start, []]],
        seen = new Set;

    while (queue.length) {
        let [curVert, [...path]] = queue.shift();
        path.push(curVert);
        if (curVert === end) return path;

        if (!seen.has(curVert) && graph[curVert]) {
            queue.push(...graph[curVert].map(v => [v, path]));
        }
        seen.add(curVert);
    }
}

console.log(bfs(graph, 1, 13));

user_14476750

For each vertex, maintain its "previous" vertex. Since there's no backtracking, once set, the previous vertex won't change. At the same time, the "previous" map will keep track of already visited vertices. When the end vertex is found, iterate the "previous" map backwards to compute the path.

const graph = {
  1: [2, 3, 4],
  2: [5, 6],
  3: [10],
  4: [7, 8],
  5: [9, 10],
  7: [11, 12],
  11: [13],
};


function bfs(graph, start, end) {
    let queue = [start]
    let prev = {[start]: null}

    while (queue.length > 0) {
        let curr = queue.shift();

        if (curr === end) {
            let path = [];

            while (curr) {
                path.unshift(curr);
                curr = prev[curr];
            }

            return path;
        }

        if (curr in graph) {
            for (let v of graph[curr]) {
                if (!(v in prev)) {
                    prev[v] = curr;
                    queue.push(v);
                }
            }
        }
    }
}

console.log(bfs(graph, 1, 13));

user_9891210
Related