Implementing a breadthFirstSearch function javascript

user_15063035 0
Viewed 120

I'm trying to implement a breadthFirstSearch function that takes in a graph, a start vertex, and an end vertex to search for, and locates the given vertex using a breadth-first search algorithm.

below is my code only using start, how would I add the end value so that if I do:

const list = {
            'A': ['B', 'C'],
            'B': ['A', 'F', 'G'],
            'C': ['A', 'H'],
            'D': [],
            'E': ['F'],
            'F': ['B', 'E', 'H', 'I'],
            'G': ['B'],
            'H': ['C', 'F'],
            'I': ['F'],
        }
const graph = new Graph(list);
breadthFirstSearch(graph, 'A', 'I')  // true

const breadthFirstSearch = (graph, start, end) => {
    const queue = [start];
    const result = [];
    const visited = {};
    let currentVertex;
    visited[start] = true;

    while(queue.length){
        currentVertex = queue.shift();
        result.push(currentVertex);
        this.adjacencyList[currentVertex].forEach(neighbor => {
            if(!visited[neighbor]){
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        });
    }
    return result;
}
breadth-first-search graph javascript
1 Answers

Tweaking your code a bit (which was close to correct in its logic) and following the less than accurate Wikipedia pseudo code on BFS, take a look at the following...

const list = {
    'A': ['B', 'C'],
    'B': ['A', 'F', 'G'],
    'C': ['A', 'H'],
    'D': [],
    'E': ['F'],
    'F': ['B', 'E', 'H', 'I'],
    'G': ['B'],
    'H': ['C', 'F'],
    'I': ['F'],
}

function breadthFirstSearch( graph, start, end ) {

  const queue = [ { parent: 'Root', node: start } ];
  const visited = {};
  let v;

  while( queue.length ) {
    v = queue.shift();
    visited[ v.node ] = v.parent;
    if ( v.node === end ) {
      return visited;
    }
    for ( let edge of graph[ v.node ] ) {
      if( !visited[ edge ] ) {
          queue.push( { parent: v.node, node: edge } );
      }
    }
  }
  
}

let result = breadthFirstSearch( list, 'A', 'I' );
console.log( result );

The critical difference is that when visiting a node, it's important to capture the parent of the node being visited. Since every node only has one parent, it is then child's play to generate the path from the goal back to the root...

user_76961620
Related