Breadth First Search – Graphs

This article covers how to implement Breadth First Search (BFS) for Graphs in Javascript. For more information on Depth First Search and the tree implementation, see the main BFS article.

Strategy
Similar to BFS for trees, the Javascript implementation for BFS for graphs is to process nodes in order. The difference is there’s no longer left/right branches, and that we need to keep track of the nodes we’ve visited. This is to prevent infinite traversal.

1. remove from next item of queue (bottom of queue)
2. process node
3. for each neighbor, if it hasn’t been visited
   • add to visited list
   • add to queue at end (which will be removed last)

let adj; //matrix of adjacencies

function BFS (node) {
  let queue=[node]; //FIFO: First In, First Out
  let visited=[]; //list of nodes we've visited already

  while (queue.length>0) { //while queue isn't empty
    const current=queue.shift(); //take from next item of queue or first item of array

    //process current node
    console.log(current);

    //add neighbors to stack and visited list
    for (let i=0; i<adj[current].length;i++) {
      if (!visited[current]) {
        visited.push(current);
        queue.push(current);
      }
    }
  }
}