Breadth First Search

breadth-first-search: The Ultimate Cheatsheet

1. Detailed Explanation

Breadth-first search (BFS) is a graph traversal algorithm that explores a graph level by level. It starts at a designated root node and visits all its neighbors before moving on to their neighbors. This systematic exploration ensures that nodes closer to the starting node are visited before those further away.

BFS is important because it solves a wide range of problems involving finding the shortest path in unweighted graphs, exploring connected components, and solving puzzles like finding paths in mazes or games. Key concepts include:

• Queue: BFS relies heavily on a queue data structure to maintain the order of node visitation. Nodes are added to the queue as they are discovered and removed as they are processed.
• Visited Set: To prevent cycles and redundant visits, BFS uses a set (or similar data structure) to track nodes that have already been explored.
• Level Order Traversal: The order in which nodes are visited is called level order traversal, reflecting the layer-by-layer exploration.

2. When to Use breadth-first-search (and When Not To)

Use BFS when:

• You need to find the shortest path between two nodes in an unweighted graph.
• You need to explore all nodes connected to a starting node.
• You’re working with a problem that can be modeled as a graph traversal where level order is important.

Don’t use BFS when:

• The graph is weighted (use Dijkstra’s algorithm or A* search instead).
• You only need to find a path, not necessarily the shortest (Depth-First Search (DFS) might be faster).
• Memory is extremely limited, as BFS can consume significant space for large graphs.

3. Core Algorithm / Data Structure Template

1. Initialization:

   • Create a queue Q and add the starting node startNode to it.
   • Create a visited set and add startNode to it.

2. Iteration:

   • While Q is not empty:
     • Dequeue a node currentNode from Q.
     • Process currentNode (e.g., print its value, check if it’s the target node).
     • For each neighbor neighbor of currentNode:
       • If neighbor is not in visited:
         • Add neighbor to Q.
         • Add neighbor to visited.

4. Code Implementations

Python

from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        print(node, end=" ")  # Process the node

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

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A') # Output: A B C D E F

Java

import java.util.*;

public class BFS {
    public static void bfs(Map<String, List<String>> graph, String startNode) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(startNode);
        visited.add(startNode);

        while (!queue.isEmpty()) {
            String node = queue.poll();
            System.out.print(node + " "); // Process the node

            for (String neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

    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("D", "E"));
        graph.put("C", Arrays.asList("F"));
        graph.put("D", new ArrayList<>());
        graph.put("E", Arrays.asList("F"));
        graph.put("F", new ArrayList<>());

        bfs(graph, "A"); // Output: A B C D E F

    }
}

C++

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

using namespace std;

void bfs(const unordered_map<string, vector<string>>& graph, const string& startNode) {
    unordered_set<string> visited;
    queue<string> q;
    q.push(startNode);
    visited.insert(startNode);

    while (!q.empty()) {
        string node = q.front();
        q.pop();
        cout << node << " "; // Process the node

        for (const string& neighbor : graph.at(node)) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

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

    bfs(graph, "A"); // Output: A B C D E F
    cout << endl;
    return 0;
}

5. Complexity Analysis

Operation	Time Complexity	Space Complexity
Best Case	O(V)	O(V)
Average Case	O(V + E)	O(V)
Worst Case	O(V + E)	O(V)

Where:

• V = Number of vertices (nodes) in the graph
• E = Number of edges in the graph

Space complexity is dominated by the queue and the visited set, both of which can hold at most all vertices in the worst case.

6. Pro Tips, Tricks, and Common Pitfalls

• Efficient Queue Implementation: Use a deque (double-ended queue) for optimal enqueue and dequeue operations.
• Handling Disconnected Graphs: BFS only explores the connected component reachable from the starting node. To explore all components, you need to iterate through all nodes, starting BFS from each unvisited node.
• Avoid Memory Leaks: Ensure proper cleanup of data structures, especially in languages with manual memory management.
• Correctness Checks: Always verify that your visited set correctly prevents cycles and redundant processing.

7. Classic Problem Examples

Example: Same Tree

Description: Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

High-Level Approach using BFS:

1. Use BFS to traverse both trees simultaneously, level by level.
2. At each level, compare the values of corresponding nodes in both trees.
3. If the values are different or the structures differ (e.g., one tree has a node where the other doesn’t), return false.
4. If both trees are fully traversed without finding any discrepancies, return true. This approach leverages the level-order nature of BFS to efficiently compare the trees’ structures. A recursive DFS solution is also common and often considered more elegant for this specific problem, but BFS demonstrates a different approach.