Graph BFS (Breadth-First Search)

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        # Process node
        process(node)
        
        # Visit neighbors
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

# Grid BFS template
def bfs_grid(grid, start_row, start_col):
    rows, cols = len(grid), len(grid[0])
    visited = set([(start_row, start_col)])
    queue = deque([(start_row, start_col, 0)])  # row, col, distance
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        row, col, dist = queue.popleft()
        
        # Process cell
        if is_target(grid[row][col]):
            return dist
        
        # Explore neighbors
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if (0 <= new_row < rows and 
                0 <= new_col < cols and 
                (new_row, new_col) not in visited and
                grid[new_row][new_col] != obstacle):
                
                visited.add((new_row, new_col))
                queue.append((new_row, new_col, dist + 1))
    
    return -1

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

void bfs(vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    queue<int> q;
    
    visited.insert(start);
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        // Process node
        process(node);
        
        // Visit neighbors
        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

// Grid BFS template
int bfsGrid(vector<vector<int>>& grid, int startRow, int startCol) {
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    queue<tuple<int, int, int>> q;  // row, col, distance
    
    visited[startRow][startCol] = true;
    q.push({startRow, startCol, 0});
    
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    while (!q.empty()) {
        auto [row, col, dist] = q.front();
        q.pop();
        
        // Process cell
        if (isTarget(grid[row][col])) {
            return dist;
        }
        
        // Explore neighbors
        for (auto& dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < rows && 
                newCol >= 0 && newCol < cols &&
                !visited[newRow][newCol] &&
                grid[newRow][newCol] != OBSTACLE) {
                
                visited[newRow][newCol] = true;
                q.push({newRow, newCol, dist + 1});
            }
        }
    }
    
    return -1;
}