Breadth-First Search Traversal in Javascript

In this modern technological world, we are required to use techniques for traversing the trees programmatically, even though our computer has a user-friendly interface for browsing across our file tree, for this purpose Breadth-first search (BFS) is the most useful algorithm.

Breadth-first search is a traversing algorithm that is used  for searching or traversing the tree or graph data structure layer by layer. Before moving on to the children node of the next depth level, it visits each node that exists at the current depth.

This article will explain how to run the Breadth-first search Algorithm using an appropriate example. So, let’s start

How Breadth-first search Algorithm works in JavaScript

The working of the Breadth-first search Algorithm comprises the following steps:

• Choose a node and create a queue with all of its neighbor nodes.
• Remove those nodes from the queue that are visited and mark them.
• Add all of its neighbor nodes in the queue.
• Repeat until the queue becomes empty or you reach your objective.

If a node is revisited before it was not marked as visited, then the program will be stopped. hence, mark nodes as visited and then it will not be searched again.

Implementation of Breadth-first search traversal Algorithm

Breadth-first search traverses trees from left to right, then moves from top to bottom (parent node to child node). ensuring that all the nodes that are present on current depth are visited.

Now, let’s have a look at a small example to understand the BFS traversal works. Here, the given undirected graph has 5 nodes “0”, “1”, “2”, “3”, and “4”:

We will now use this traversal algorithm on the specified graph.

Step 1: Initialization of the queue

First of all, we have to initialize the queue “q”:

Step 2: Choose starting node

Next, we will choose the starting node. For this purpose, we will select “0” as starting node and mark it as visited:

Step 3: Unvisited adjacent nodes of starting node

Starting node is visited and marked; now, we will check its adjacent nodes. In the below illustration, starting node “0” has three unvisited adjacent nodes “1”, “2”, and “3”; however, we will choose node “1” because of the sequence of counting. Then, mark it as visited and add it to the queue:

Now, the unvisited node of “0” is “2”, which is also marked as visited and added to the queue:

Then, we will visit the last unvisited adjacent node, which is “3”, marked it as visited and enqueue it:

Step 4: Dequeue the starting node

Now our selected starting node “0” does not have any unvisited adjacent nodes, So we will remove the queue and search for the node “1”:

Step 5: Check the unvisited adjacent of node “1”

At this point, node “1” have node “4” as its unvisited adjacent:

Node “4” is now marked as visited and added to the queue. Now, we have no more unvisited nodes. However, according to the algorithm, we will obtain all unvisited nodes and continue to remove the node from the queue as per the procedure. The program will end when the queue becomes empty.

Let’s implement an example to check how Breadth-first Search works in JavaScript.

How to implement Breadth-first Search Traversal in JavaScript

To implement Breadth-first Search Traversal in JavaScript, first of all we will create a graph:

The above-given graph which is used to illustrate the breadth-first search has “5” nodes. So, here we will define “5” nodes:

Now, create a “visited[ ]” array that will be used to store visited nodes and the length of this array will be set according to the number of nodes:

Next, we will define the “createGraph()” function for the purpose of creating a graph and adding nodes to it. Then the “for” loop will execute till the length of the graph. Inside the loop, there is a two-dimensional array that is use to represent the graph edges initialized with “0”:

Then, we will define the “addEdge()” function that accepts two arguments “a” and “b”. This function will check the edge between two nodes. If an edge is found between two nodes, then the “addEdge()” function will replace the “0” entry with “1” in the created graph(two-dimensional array).  Also, adding “1” indicates that the passed nodes argument have an edge in between them:

Now, we will define the “breadthFirstSearch()” function. First, we will create an empty “queue”. At start, all of the nodes are unvisited so they are marked as false  with a “visited[i] = false” statement. Then, we will select the starting “node” that is passed as argument to the “breadthFirstSearch()” function and mark it visited. The “queue.push()” method will push the “node” to the queue then the “while” loop will execute till the length of the queue. This loop will check the edges of the “currentNode” with the remaining node.

Inside the “for” loop, the added “if” condition “[currentNode][j] === 1” will check the edges between the “currentNode” and the remaining “j” nodes. In case, if both nodes have an edge between them and the corresponding “j” node is not visited yet, then it will be marked as “visited” and pushed to the “queue”:

Next, we will call the “createGraph()” function and pass the “nodes” as argument:

After doing so, specify the edges of node “0, 1, 2, 3” with the “addEdge()” function, as demonstrated in the above-given diagram:

Here, “0” is passed as starting node to the BFS() function which will perform the further operation:

BFS() method will traverse the graph nodes and output the visited nodes on console:

That was all useful information about Breadth-first search traversal algorithm in JavaScript. Go for further research if required.

Conclusion

Breadth-first search (BFS) is a traversing algorithm that is used  for searching or traversing the tree or graph data structure layer by layer. Before moving on to the children node of the next depth level, it visits each node that exists at the current depth. In this article, we have briefly discussed the Breadth-first search traversal JavaScript algorithm and its working with the help of a suitable example.