Breadth First Search Algorithm: Exploring the Basics for Efficient Programming

What is Breath First Search Algorithm?

Breadth First Search (BFS) is a traversal algorithm that explores all the nodes of a graph or tree by visiting all the nodes at a given level before moving on to the next level. In JavaScript, BFS can be implemented using a queue data structure.

Here’s an example implementation of BFS in JavaScript:

class Graph {
  constructor() {
    this.vertices = [];
    this.adjList = new Map();
  }

  addVertex(v) {
    this.vertices.push(v);
    this.adjList.set(v, []);
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v);
  }

  bfs(startingNode) {
    const visited = new Set();
    const queue = [];

    visited.add(startingNode);
    queue.push(startingNode);

    while (queue.length > 0) {
      const currentNode = queue.shift();
      console.log(currentNode);

      const neighbors = this.adjList.get(currentNode);
      for (let neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
}

Here, the Graph class represents an undirected graph. The addVertex method adds a vertex to the graph, and the addEdge method adds an edge between two vertices. The bfs method initiates the BFS traversal by creating a visited set to keep track of visited nodes and queue to store the nodes that need to be visited. The starting node is added to both the visited set and the queue.

The while loop continues to run as long as there are nodes in the queue. On each iteration, the first node in the queue is removed and stored in currentNode. The method then logs the current node to the console to show the order in which the nodes are visited.

The method then retrieves the neighbors of the current node from the adjacency list and loops over each neighbor. If the neighbor has not been visited before, it is added to the visited set and the queue to be visited later.

Here’s an example of how to use the Graph class to perform a BFS traversal:

const graph = new Graph();
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
graph.bfs(1);

In this example, a Graph object is created, and vertices and edges are added to the graph. The bfs method is then called with the starting node of 1, and the order in which the nodes are visited is logged to the console:

1
2
3
4
5

It’s worth noting that BFS has a time complexity of O(V + E), where V is the number of vertices in the graph and E is the number of edges. Unlike DFS, BFS does not suffer from the recursion depth issue and is often the preferred traversal algorithm for larger graphs.