Breadth-First Search (BFS)

Generated on 2025-07-10 01:56:20 Algorithm Cheatsheet for Technical Interviews

---

Breadth-First Search (BFS) Cheatsheet

1. Quick Overview

• What is it? A graph traversal algorithm that explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It systematically explores a graph level by level.
• When to use it?
  • Finding the shortest path in an unweighted graph.
  • Graph traversal when you need to explore all neighbors first.
  • Level order traversal of a tree.
  • Finding connected components in a graph.
  • Social network analysis (finding friends of friends).

2. Time & Space Complexity

Operation	Complexity	Explanation
Time	O(V + E)	V = number of vertices (nodes), E = number of edges. Visits each node and edge once.
Space	O(V)	In the worst-case scenario (e.g., a complete graph), the queue might hold all vertices.

3. Implementation

Python

from collections import deque

def bfs(graph, start_node):
    """
    Performs Breadth-First Search on a graph.

    Args:
        graph: A dictionary representing the graph, where keys are nodes
               and values are lists of their neighbors.
        start_node: The node to start the search from.

    Returns:
        A list of nodes visited in BFS order.
    """
    visited = set()  # Keep track of visited nodes
    queue = deque([start_node]) # Use a deque for efficient FIFO
    visited_order = []

    visited.add(start_node)  # Mark the starting node as visited

    while queue:
        node = queue.popleft()  # Dequeue the next node
        visited_order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return visited_order

# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

start_node = 'A'
bfs_result = bfs(graph, start_node)
print(f"BFS traversal starting from {start_node}: {bfs_result}") # Output: BFS traversal starting from A: ['A', 'B', 'C', 'D', 'E', 'F']

Java

import java.util.*;

public class BFS {

    public static List<String> bfs(Map<String, List<String>> graph, String startNode) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        List<String> visitedOrder = new ArrayList<>();

        visited.add(startNode);
        queue.offer(startNode);

        while (!queue.isEmpty()) {
            String node = queue.poll();
            visitedOrder.add(node);

            for (String neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        return visitedOrder;
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));

        String startNode = "A";
        List<String> bfsResult = bfs(graph, startNode);
        System.out.println("BFS traversal starting from " + startNode + ": " + bfsResult); // Output: BFS traversal starting from A: [A, B, C, D, E, F]
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<char> bfs(unordered_map<char, vector<char>>& graph, char startNode) {
    unordered_set<char> visited;
    queue<char> q;
    vector<char> visitedOrder;

    visited.insert(startNode);
    q.push(startNode);

    while (!q.empty()) {
        char node = q.front();
        q.pop();
        visitedOrder.push_back(node);

        for (char neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }

    return visitedOrder;
}

int main() {
    unordered_map<char, vector<char>> graph = {
        {'A', {'B', 'C'}},
        {'B', {'A', 'D', 'E'}},
        {'C', {'A', 'F'}},
        {'D', {'B'}},
        {'E', {'B', 'F'}},
        {'F', {'C', 'E'}}
    };

    char startNode = 'A';
    vector<char> bfsResult = bfs(graph, startNode);

    cout << "BFS traversal starting from " << startNode << ": ";
    for (char node : bfsResult) {
        cout << node << " ";
    }
    cout << endl; // Output: BFS traversal starting from A: A B C D E F
    return 0;
}

4. Common Patterns

• Level Order Traversal (Trees): Modify the basic BFS to keep track of the level of each node.
• Shortest Path in Unweighted Graphs: Keep track of the distance from the starting node. The first time you reach a node, you’ve found the shortest path to it.
• Connected Components: Iterate through all nodes in the graph. If a node hasn’t been visited yet, start a BFS from that node. Each BFS explores one connected component.
• Flood Fill: Starting from a given point, change the color of all connected cells with the same original color to a new color.

5. Pro Tips

• Use a Queue: BFS relies on a FIFO (First-In, First-Out) queue. Use collections.deque in Python, LinkedList in Java, and std::queue in C++ for efficient queue operations.
• Avoid Cycles: The visited set/hashset/unordered_set is crucial to prevent infinite loops in graphs with cycles.
• Distance Tracking: If you need to find the shortest path length, add a distance array/map and update it during the BFS. Initialize all distances to infinity except for the starting node.
• Space Optimization: For very large graphs, consider using an adjacency list representation instead of an adjacency matrix to save space. Adjacency lists store only the actual edges.
• Bidirectional BFS: If you know the start and end nodes, consider using bidirectional BFS. Start BFS from both nodes simultaneously. When the two searches meet, you’ve found the shortest path. This can significantly reduce the search space.

6. Practice Problems

1. LeetCode 102. Binary Tree Level Order Traversal: Given a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
2. LeetCode 200. Number of Islands: Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
3. LeetCode 127. Word Ladder: A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
   • Every adjacent pair of words differs by a single letter.
   • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
   • sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

7. Templates

Python Template

from collections import deque

def bfs_template(graph, start_node, target_node=None):
    """
    BFS template for various graph problems.

    Args:
        graph: The graph representation (e.g., adjacency list).
        start_node: The node to start BFS from.
        target_node (optional): The target node to search for. Defaults to None.

    Returns:
        Relevant data based on the problem (e.g., shortest path, list of nodes, etc.).
    """

    visited = set()
    queue = deque([(start_node, 0)])  # Store node and distance/level
    visited.add(start_node)

    while queue:
        node, distance = queue.popleft()

        # Process the current node (e.g., check if it's the target)
        if target_node and node == target_node:
            return distance  # Found the target, return the distance

        # Explore neighbors
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))

    # Target not found or other completion logic
    return -1 # or None or appropriate default value

Java Template

import java.util.*;

public class BFSTemplate {

    public static int bfsTemplate(Map<String, List<String>> graph, String startNode, String targetNode) {
        Set<String> visited = new HashSet<>();
        Queue<Pair<String, Integer>> queue = new LinkedList<>(); // Store node and distance

        visited.add(startNode);
        queue.offer(new Pair<>(startNode, 0));

        while (!queue.isEmpty()) {
            Pair<String, Integer> current = queue.poll();
            String node = current.getKey();
            int distance = current.getValue();

            // Process the current node (e.g., check if it's the target)
            if (targetNode != null && node.equals(targetNode)) {
                return distance; // Found the target, return the distance
            }

            // Explore neighbors
            for (String neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(new Pair<>(neighbor, distance + 1));
                }
            }
        }

        // Target not found or other completion logic
        return -1; // or appropriate default value
    }

    // Helper class for storing pairs of data
    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }

    public static void main(String[] args) {
        // Example Usage (replace with your specific graph)
        Map<String, List<String>> graph = new HashMap<>();
        // ... populate your graph ...

        String startNode = "A";
        String targetNode = "F";
        int shortestDistance = bfsTemplate(graph, startNode, targetNode);

        System.out.println("Shortest distance from " + startNode + " to " + targetNode + ": " + shortestDistance);
    }
}

C++ Template

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int bfsTemplate(unordered_map<char, vector<char>>& graph, char startNode, char targetNode) {
    unordered_set<char> visited;
    queue<pair<char, int>> q; // Store node and distance

    visited.insert(startNode);
    q.push({startNode, 0});

    while (!q.empty()) {
        char node = q.front().first;
        int distance = q.front().second;
        q.pop();

        // Process the current node (e.g., check if it's the target)
        if (targetNode != '\0' && node == targetNode) {
            return distance; // Found the target, return the distance
        }

        // Explore neighbors
        for (char neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push({neighbor, distance + 1});
            }
        }
    }

    // Target not found or other completion logic
    return -1; // or appropriate default value
}

int main() {
    // Example Usage (replace with your specific graph)
    unordered_map<char, vector<char>> graph = {
        {'A', {'B', 'C'}},
        {'B', {'A', 'D', 'E'}},
        {'C', {'A', 'F'}},
        {'D', {'B'}},
        {'E', {'B', 'F'}},
        {'F', {'C', 'E'}}
    };

    char startNode = 'A';
    char targetNode = 'F';
    int shortestDistance = bfsTemplate(graph, startNode, targetNode);

    cout << "Shortest distance from " << startNode << " to " << targetNode << ": " << shortestDistance << endl;
    return 0;
}

This cheatsheet provides a comprehensive overview of BFS, covering its core concepts, implementation details, common patterns, and helpful tips. The included templates make it easy to adapt BFS to various graph-related problems. Remember to adapt the templates and problem-solving strategies to the specific requirements of each problem. Good luck!