Breadth-First Search (BFS)

Breadth-First Search (BFS)

Welcome to Breadth-First Search (BFS), a fundamental graph traversal algorithm. BFS explores a graph layer by layer, visiting all neighbors at the present depth before moving on to the next level. This systematic approach makes it ideal for finding the shortest path in unweighted graphs and for solving a variety of connectivity problems.

---

1. The BFS Algorithm: A Layer-by-Layer Exploration

Imagine a ripple effect in a pond. BFS works similarly. It starts at a given "source" vertex and explores its immediate neighbors first. Then, for each of those neighbors, it explores their unexplored neighbors, and so on. This process continues until all reachable vertices have been visited.

To keep track of the vertices to visit, BFS uses a Queue data structure, which perfectly complements its layer-by-layer exploration strategy.

---

2. Core BFS Process

The BFS algorithm can be broken down into the following steps:

1. Initialization:

   • Create a queue and add the starting (source) vertex to it.
   • Create a visited set or array to keep track of visited vertices, and mark the source as visited.
   • Optionally, create arrays to store distance and parent for shortest path calculations.

2. Traversal Loop:

   • While the queue is not empty, perform the following steps:
     • Dequeue: Remove the vertex at the front of the queue. Let's call it u.
     • Process Neighbors: For each neighbor v of u:
       • If v has not been visited:
         • Mark v as visited.
         • (Optional) Set distance[v] = distance[u] + 1.
         • (Optional) Set parent[v] = u.
         • Enqueue: Add v to the back of the queue.

3. Completion:

   • Once the queue is empty, all reachable vertices have been visited.

---

3. BFS Applications

BFS is a versatile algorithm with several important applications.

3.1. Single-Source Shortest Paths (Unweighted)

In an unweighted graph, BFS is guaranteed to find the shortest path (in terms of the number of edges) from a source vertex to all other reachable vertices.

• Concept: Since BFS explores layer by layer, it finds all vertices at distance 1, then all vertices at distance 2, and so on. This naturally yields the shortest path.

• Implementation:

  function bfsShortestPath(adj, src) {
    const N = adj.length;
    const dist = Array(N).fill(Infinity);
    const parent = Array(N).fill(-1);
    const q = [src];
  
    dist[src] = 0;
  
    let head = 0;
    while (head < q.length) {
      const u = q[head++];
      for (const v of adj[u]) {
        if (dist[v] === Infinity) {
          dist[v] = dist[u] + 1;
          parent[v] = u;
          q.push(v);
        }
      }
    }
    return { dist, parent };
  }
  

3.2. Bipartite Check

A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. BFS can be used to check for this property.

• Concept: As we traverse the graph with BFS, we can assign alternating "colors" (e.g., 0 and 1) to each layer of vertices. If we ever find an edge connecting two vertices of the same color, the graph is not bipartite.

• Implementation:

  function isBipartite(adj) {
    const N = adj.length;
    const color = Array(N).fill(-1);
  
    for (let startNode = 0; startNode < N; startNode++) {
      if (color[startNode] === -1) {
        const q = [startNode];
        color[startNode] = 0;
        let head = 0;
  
        while (head < q.length) {
          const u = q[head++];
          for (const v of adj[u]) {
            if (color[v] === -1) {
              color[v] = 1 - color[u]; // Assign alternating color
              q.push(v);
            } else if (color[v] === color[u]) {
              return false; // Same color neighbors, not bipartite
            }
          }
        }
      }
    }
    return true;
  }
  

---

4. Complexity and Tips

• Time Complexity: O(N + M), where N is the number of vertices and M is the number of edges. This is because each vertex and each edge is visited exactly once.

• Space Complexity: O(N) in the worst case, to store the queue and the visited array.

• Tips:

  • For performance in JavaScript, use an array with a head/tail pointer for the queue to avoid the O(N) cost of Array.prototype.shift().
  • Always mark a vertex as visited when you enqueue it, not when you dequeue it. This prevents adding the same vertex to the queue multiple times.

---

Key Takeaway: BFS is a layer-by-layer traversal algorithm that uses a queue. Its systematic exploration makes it the perfect tool for finding the shortest path in unweighted graphs and for checking properties like bipartiteness, all with a time complexity of O(N + M).