1. BFS

Generic Template

void bfs(int start, vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);   // Track visited nodes
    queue<int> q;                              // Queue for BFS

    q.push(start);                             // Push starting node
    visited[start] = true;                     // Mark it visited

    while (!q.empty()) {

        int node = q.front();                  // Get front node
        q.pop();                               // Remove it

        // Process the current node
        // cout << node << " ";

        for (int neighbor : adj[node]) {  // Visit all adjacent nodes

            if (!visited[neighbor]) {

                visited[neighbor] = true;      // Mark visited
                q.push(neighbor);              // Add to queue
            }
        }
    }
}

Source BFS

Grid Traversal

// Push starting cell(s)
queue<pair<int,int>> q; 

/*
Useful for
	Store Distance: Shortest Path, Distance from source
	Store Time: 
*/
queue<pair<pair<int,int>, int>> q;

// Push one starting cell [Single Source BFS]
q.push({startRow, startCol});
// Push more starting cells  [Multi Source BFS]
for (...) q.push(...);

// 4 Directions
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

while (!q.empty()) {

    auto cell = q.front();
    q.pop();

    int row = cell.first;
    int col = cell.second;

    // Explore 4 directions
    for (int k = 0; k < 4; k++) {

        int nr = row + dr[k];
        int nc = col + dc[k];

        if (nr >= 0 && nr < rows &&
            nc >= 0 && nc < cols) {

            // Process (nr, nc)
        }
    }
}

Grid Level/Distance

// Push all source cells
queue<pair<int,int>> q;

for (...) {

    if (source)
        q.push(...);
}

// 4 Directions
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

while (!q.empty()) {

    int size = q.size();      // Current level

    while (size--) {

        auto cell = q.front();
        q.pop();

        int row = cell.first;
        int col = cell.second;

        // Explore 4 directions
        for (int k = 0; k < 4; k++) {

            int nr = row + dr[k];
            int nc = col + dc[k];

            if (nr >= 0 && nr < rows &&
                nc >= 0 && nc < cols) {

                // Process (nr, nc)
            }
        }
    }

    // Finished one level
    // minute++, distance++, steps++, etc.
}

Applications

1. Working with grids, adjacency lists, or networks
2. Structure can contain cycles or duplicate paths
3. Need to find the shortest number of steps
4. Exploring possible states