Breadth First Search (BFS): A Comprehensive Guide

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph or all the nodes of a tree at the present depth before moving to the nodes at the next depth level. It's widely used for finding the shortest path on unweighted graphs and for level-order traversal of trees.

How BFS Works

  1. Start at a chosen node (often called the root node for trees).
  2. Explore all the neighboring nodes at the present depth before moving on to the nodes at the next depth level.
  3. Typically implemented using a queue data structure to keep track of the nodes to be explored.
  4. Each node is processed only once.

Implementation in Java

Here's a basic implementation of BFS for a graph in Java:

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer>[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int n : adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Breadth First Traversal (starting from vertex 2)");
        g.BFS(2);
    }
}

Implementation in C++

Here's the same implementation in C++:

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

class Graph {
    int V;
    list<int> *adj;

public:
    Graph(int V);
    void addEdge(int v, int w);
    void BFS(int s);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::BFS(int s) {
    vector<bool> visited(V, false);
    queue<int> queue;

    visited[s] = true;
    queue.push(s);

    while(!queue.empty()) {
        s = queue.front();
        cout << s << " ";
        queue.pop();

        for (auto adjacent : adj[s]) {
            if (!visited[adjacent]) {
                visited[adjacent] = true;
                queue.push(adjacent);
            }
        }
    }
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    cout << "Breadth First Traversal (starting from vertex 2) \n";
    g.BFS(2);

    return 0;
}

Let's look at some popular interview problems related to BFS and their solutions in both Java and C++.

1. Level Order Traversal of a Binary Tree

Problem: Given a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Java Solution:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }
}

C++ Solution:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            result.push_back(currentLevel);
        }

        return result;
    }
};

Explanation: This problem uses BFS to traverse the tree level by level. We use a queue to keep track of nodes at each level, and we process all nodes at the current level before moving to the next.

2. Word Ladder

Problem: Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list.

Java Solution:

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentWord = queue.poll();
                char[] wordChars = currentWord.toCharArray();

                for (int j = 0; j < wordChars.length; j++) {
                    char originalChar = wordChars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        wordChars[j] = c;
                        String newWord = new String(wordChars);

                        if (newWord.equals(endWord)) return level + 1;

                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                    wordChars[j] = originalChar;
                }
            }
            level++;
        }

        return 0;
    }
}

C++ Solution:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return 0;

        queue<string> q;
        q.push(beginWord);
        int level = 1;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string currentWord = q.front();
                q.pop();

                for (int j = 0; j < currentWord.length(); j++) {
                    char originalChar = currentWord[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        currentWord[j] = c;

                        if (currentWord == endWord) return level + 1;

                        if (wordSet.count(currentWord)) {
                            q.push(currentWord);
                            wordSet.erase(currentWord);
                        }
                    }
                    currentWord[j] = originalChar;
                }
            }
            level++;
        }

        return 0;
    }
};

Explanation: This problem uses BFS to find the shortest transformation sequence. We start with the beginWord and explore all possible one-letter transformations at each step, checking if they exist in the word list. The first time we reach the endWord is guaranteed to be the shortest path due to the nature of BFS.

These problems demonstrate how BFS can be applied to solve complex problems efficiently, especially when dealing with shortest paths or level-order traversals. Understanding these applications is crucial for mastering BFS and performing well in coding interviews.