Breadth first search(BFS) using Javascript

Breadth first search(bfs) is a graph traversal method. In bfs, we explore a vertex and then go to next vertex. Exploring a vertex means, visiting the adjacent vertex.

Graph are set of nodes connected to each other and nodes are connected to each other through edges.

A tree is also a graph, but the only difference is that , graph have cycles.

Graphs are of two types:

• Directed Graph (direction is specified)
• Undirected Graph (no direction is given)

Bfs parse the current level first them move to next level

Bfs is also known as level order traversal.

Before we jump into BFS, let’s understand how we can represent graphs so that we can use them in our code. There are two ways to do it,

• Using Adjacency matrix(array)
• Using Adjacency list

For this blog, let’s use Adjacency Matrix which is nothing but 2-D array representation of our graph.

Let’s say we have a graph that looks like this:

Undirected Graph

This is an undirected graph as there is no direction defined for the edges. The matrix will always be n*n. N represents the nodes in a graph. The adjacency matrix for this graph will be.

Here 0 means , node is not connected and 1 means node is connected. The diagonals of this matrix is representing 0 means there are no self connecting nodes(loop).

For understanding the working of BFS, let’s take the above matrix and try to find the node count(no of nodes that we need to visit) to visit another nodes from a root node.

We’ll make use of Queue data structure

Sudo code for implementation of BFS is:

- Initially, we'll create a hashmap to represent each node with a distance.
- Then, we set the distance to all nodes as Infinity.
- we'll set the root node count as 0.
- Initialise a queue and push the root node to the queue.
- Then we need to create a while loop that will run until our queue is empty 
and all the nodes are processed.
- Do a dequeue operation on queue(getting first value from the queue) and
 get the node.
- Find the connecting neighbours(means with value 1) 
  of the node(which is recently dequeued).
- if the value of the neighour is infinity then we need to set the value
 for that node in our hashmap to (currentRootValue in haspmap) +1 
- push the neighbour to the queue.
- At last, outside the while loop, we need to return the hashmap with updated
node counts.

Let’s jump into the code for implementation of bfs to find the node count for a given root node to all the nodes in the graph.

/**
 * Traversing through the graph
 * @param {Array} graph , graph matrix
 * @param {Number} rootNode , root node to start from
 */
const bfs = (graph, rootNode) => {
  // initializing a hashmap to store the node counts
  let nodeDistance = {};
  // set all distance for nodes to infinity
  for (let i = 0; i < graph.length; i++) {
    nodeDistance[i] = Infinity;
  }

  // set distance from root node to root node is 0
  nodeDistance[rootNode] = 0;

  // creating a queue to keep track of nodes to visit
  let queue = [rootNode];


  // iterate while we have nodes in queue
  while (queue.length) {
    const currentNode = queue.shift(); // fetch first element in queue

    //get all the nodes connected to current node
    const currentConnectedNodes = graph[currentNode];

    // array to store all the nodes that are connected
    let neighborIdx = [];
    currentConnectedNodes.forEach((element, idx) => {
      if (element == 1) {
        // 1 means connected
        neighborIdx.push(idx);
      }
    });

    // finding the distance
    for (let i = 0; i < neighborIdx.length; i++) {
      if (nodeDistance[neighborIdx[i]] === Infinity) {
        // value is not set as per now
        nodeDistance[neighborIdx[i]] = nodeDistance[currentNode] + 1;
        // push neighbour to queue
        queue.push(neighborIdx[i]);
      }
    }
  }

  // return hashmap with updated distance
  return nodeDistance;
};

If we call the function (bfs) with our matrix and try to find the distance from b which is at index 1 then it should look like this:

// 2-d representation of an undirected graph
const newbfsGraph = [
  [0, 1, 1, 1],
  [1, 0, 1, 0],
  [1, 1, 0, 0],
  [1, 0, 0, 0],
];

// in our adjacency matrix b is at 1 index.
console.log(bfs(newbfsGraph, 1));

The response will be something like this:

• Visiting a will take 1, we have to travel from b to a.
• Visiting b will take 0 , as we are starting from b itself.
• Visiting c will take 1 as well, as we are directly connected from b to c.
• Visiting d will take 2 , as we have to move from b to a first then from a to d.

In this approach we are first visiting the neighbours of current node, then we move on to the neighbours of other nodes.

Hope you understand the working of bfs, it is quite easy if you understand and practice it well.

Stay tuned for more to come, If you are new here, do checkout our Algorithms with Javascript blog, we are covering few of the most commonly used algorithms.

In the next blog, we’ll go through Depth first search.