Breadth First Search Algorithm In Javascript | letsbug

 

    In this article we are looking at how we can implement the Breadth First Search in Javascript with recursion. We are not going to waste time so let's just start.

Breadth First Search In Javascript

    In the below code first we have declared a graph. And this representation of graph is called adjacency matrix. We have represented the nodes with the key in the graph and connection to other nodes is represented with the value array of the graph object.

    Then we have the traverse arrow function which takes in two parameter one is the graph object itself and a starting node. And the function start with creating a visited empty object and a array called queue with the connection of the first node of graph.

    And then we initialize the visited object with the first node of the and set it to true. So that we know that we have visited it and do not fall into a infinite cycle. 

    We then have a helper function inside of our main function. Which will do the recursion for us. It takes in only one parameter the node. This function if until the length of the queue is empty. Which means that there is not node to visit.

    While there is some element in the queue to visit. We visit the node and then remove it from the queue cause we now have visited it. We also print the value of that node. And check its connections or neighbor. And if it has a neighbor which is not visited by us. Then we put that neighbor to the queue to visit them later. And we again call the bfsRecursion helper function to traverse that particular neighbor.

    Then we come out of the helper function and call the helper function with first node.

    This was how I have implemented it. There are many way you can implement Breadth First Search in many different languages.

code:

const graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
//bfs traversal in graph using recursion
const traverse = (graph, start) => {
    const visited = {};
    const queue = [start];
    visited[start] = true;
    const bfsRecursion = (node) => {
        if (queue.length) {
            const node = queue.shift();
            console.log(node);
            for (let neighbor of graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                    bfsRecursion(neighbor);
                }
            }
        }
    }
    bfsRecursion(start);
}
traverse(graph, 'A'); //A B C D E f

Thank you