Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices in a graph by visiting them in layers.

It starts from a source vertex and explores all of the neighbor vertices at the present layer before moving on to the vertices at the next layer.

BFS is commonly used in graph problems like finding the shortest path, connected components, and solving puzzles.

Algorithm

The BFS algorithm follows these steps:

1. Start from a vertex V and mark it as visited.
2. Enqueue V into a queue.
3. While the queue is not empty:
   • Dequeue a vertex U from the queue.
   • For each unvisited neighbor W of U, mark W as visited and enqueue W.
4. Repeat the process until the queue is empty.

Here's a basic template of a BFS algorithm in JavaScript:

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  visited.add(start);

  while (queue.length > 0) {
    const current = queue.shift();

    for (const neighbor of graph[current]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

Example

Given a graph defined as an adjacency list. Each node has a list of its neighbors. You are required to print all nodes in the graph using BFS algorithm.

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const bfs = (graph, start) => {
  const visited = new Set();
  const queue = [start];

  visited.add(start);

  while (queue.length > 0) {
    const current = queue.shift();

    for (const neighbor of graph[current]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
};

Time Complexity

The time complexity of the BFS algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity

The space complexity of the BFS algorithm is O(V), where V is the number of vertices in the graph. This space is used to store the visited vertices and the queue.