Breadth-First Search (BFS)

What is BFS?

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores vertices (or nodes) of a graph layer by layer. It starts from a selected source node and visits all its neighbors before moving to the next level neighbors.

BFS is widely used for solving problems involving shortest paths in unweighted graphs, connectivity checks, cycle detection, and more.

How Does BFS Work?

• It uses a queue to keep track of nodes to visit next.
• Each node is marked as visited once it's added to the queue to prevent cycles or revisits.
• The algorithm continues until the queue is empty, meaning all reachable nodes have been visited.

Complexity Analysis

• Time Complexity: O(V + E), where V = number of vertices and E = number of edges. Every vertex and edge is visited once.
• Space Complexity: O(V), due to the visited array and the queue.

Easy Problems

1. Check if a Graph is Bipartite

A graph is bipartite if it is possible to color its vertices with two colors such that no two adjacent vertices have the same color. BFS can be used to try to color the graph in this way, level by level.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool isBipartite(vector<vector<int>>& graph, int V) {
    vector<int> color(V, -1); // -1 means unvisited
    for (int start = 0; start < V; ++start) {
        if (color[start] == -1) {
            queue<int> q;
            q.push(start);
            color[start] = 0;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : graph[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u]; // alternate color
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false; // same color on both ends of an edge
                    }
                }
            }
        }
    }
    return true;
}
  

2. Find Shortest Path in an Unweighted Graph

BFS finds the shortest path from a source to all other vertices in an unweighted graph because it explores vertices in order of their distance from the source.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfsShortestPath(vector<vector<int>>& graph, int src, vector<int>& dist) {
    int V = graph.size();
    vector<bool> visited(V, false);
    queue<int> q;
    dist[src] = 0;
    visited[src] = true;
    q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}
  

Intermediate Problems

1. Number of Islands

Treat the grid as a graph. Each land cell ('1') is a node connected to its adjacent land cells. Use BFS to explore and sink each island.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int,int>> q;
    q.push({i, j});
    grid[i][j] = '0'; // mark as visited
    int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (auto& d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {
                grid[nx][ny] = '0';
                q.push({nx, ny});
            }
        }
    }
}

int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == '1') {
                bfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}
  

2. Word Ladder - Shortest Transformation Sequence

Transform one word into another by changing one letter at a time, using only valid intermediate words. BFS is used to explore all valid one-letter transformations.

#include <iostream>
#include <unordered_set>
#include <queue>
using namespace std;

int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
    queue<pair<string, int>> q;
    q.push({beginWord, 1});
    while (!q.empty()) {
        auto [word, level] = q.front(); q.pop();
        if (word == endWord) return level;
        for (int i = 0; i < word.size(); ++i) {
            string next = word;
            for (char c = 'a'; c <= 'z'; ++c) {
                next[i] = c;
                if (wordList.count(next)) {
                    wordList.erase(next); // avoid revisiting
                    q.push({next, level + 1});
                }
            }
        }
    }
    return 0;
}
  

Hard Problem

Maze with Obstacles - Shortest Path with Eliminations

You are allowed to eliminate up to k obstacles in a grid to find the shortest path from the top-left to the bottom-right. BFS is extended by tracking the number of remaining eliminations as part of the state.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int shortestPath(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> visited(m, vector<int>(n, -1));
    queue<tuple<int, int, int>> q;
    q.push({0, 0, k});
    visited[0][0] = k;
    int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    int steps = 0;
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            auto [x, y, remaining] = q.front(); q.pop();
            if (x == m-1 && y == n-1) return steps;
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    int nk = remaining - grid[nx][ny];
                    if (nk > visited[nx][ny]) {
                        visited[nx][ny] = nk;
                        q.push({nx, ny, nk});
                    }
                }
            }
        }
        steps++;
    }
    return -1;
}
  

Conclusion

BFS is a powerful and versatile graph traversal technique useful for many problems including shortest paths, connectivity, and grid-based traversal. Understanding how it works and when to use it is essential for efficient algorithm design.