C++ In Practice - Graph Traversals DFS BFS

Graph Traversal (DFS / BFS) (C++11 Deep Dive)

Graph algorithms in C++11 require careful management of memory (adjacency lists), state (visited arrays), and iterative structures (stack/queue).

Data Structures for Graphs

The simplest representation is the Adjacency List.

• Weighted: vector<vector<pair<int, int>>> adj; (Node -> {Neighbor, Weight})
• Unweighted: vector<vector<int>> adj;
• Implicit (Grid): vector<vector<int>> grid; (Neighbors are calculated via offsets).

---

1. Depth-First Search (DFS)

Concept: Explore deep, backtrack.

Stack Implementation: std::stack.

Recursion Implementation: System call stack.

Usage: Detecting cycles, connectivity, topological sort, pathfinding (not shortest).

C++11 Recursive Template (Grid Example - "Number of Islands"): In grid problems, we often mutate the grid itself to mark visited nodes ('1' -> '0') to save O(NM) space of a separate visited array.

#include <vector>

class Solution {
public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        if (grid.empty()) return 0;
        
        int count = 0;
        int rows = grid.size();
        int cols = grid[0].size();
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

private:
    void dfs(std::vector<std::vector<char>>& grid, int r, int c) {
        // Boundary and validity checks
        if (r < 0 || r >= grid.size() || 
            c < 0 || c >= grid[0].size() || 
            grid[r][c] == '0') {
            return;
        }

        // Mark as visited (sink the island)
        grid[r][c] = '0';

        // Visit 4 neighbors
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
};

---

2. Breadth-First Search (BFS)

Concept: Explore layer by layer.

Queue Implementation: std::queue.

Usage: Shortest Path in unweighted graphs.

C++11 Template (Word Ladder - Shortest Path): We use std::unordered_set for O(1) lookups of the word list.

#include <vector>
#include <string>
#include <queue>
#include <unordered_set>

int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
    // 1. Put all words in a set for O(1) checks
    std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
    if (dict.find(endWord) == dict.end()) return 0;

    // 2. Queue stores {word, level}
    std::queue<std::pair<std::string, int>> q;
    q.push({beginWord, 1});

    // 3. BFS
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        std::string word = current.first;
        int level = current.second;

        if (word == endWord) return level;

        // Try changing every character
        for (int i = 0; i < word.size(); ++i) {
            char originalChar = word[i];
            
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == originalChar) continue;
                
                word[i] = c; // Mutate in place
                
                if (dict.find(word) != dict.end()) {
                    q.push({word, level + 1});
                    dict.erase(word); // Mark visited by removing from set
                }
            }
            word[i] = originalChar; // Restore for next iteration
        }
    }
    return 0;
}

---

3. Clone Graph (DFS + HashMap)

Problem: Deep copy of a connected graph.

Key Insight: Use a HashMap (Node* -> Node*) to map original nodes to their clones to handle cycles and reuse created nodes.

#include <vector>
#include <unordered_map>

// Definition for a Node.
class Node {
public:
    int val;
    std::vector<Node*> neighbors;
    Node(int _val) : val(_val) {}
};

class Solution {
    std::unordered_map<Node*, Node*> copies;

public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;

        // If strictly graph is a DAG or tree, we don't need map for cycles.
        // But general graphs require map to avoid infinite loops.
        if (copies.find(node) != copies.end()) {
            return copies[node];
        }

        // Create clone
        Node* clone = new Node(node->val);
        copies[node] = clone;

        // Recursively clone neighbors
        for (Node* neighbor : node->neighbors) {
            clone->neighbors.push_back(cloneGraph(neighbor));
        }

        return clone;
    }
};

---

4. Topological Sort (Kahn's Algorithm - BFS)

Problem: Course Schedule (Detect cycle or return order).

Concept: Uses Indegree (number of incoming edges).

1. Compute indegree for all nodes.
2. Push nodes with 0 indegree to queue.
3. Process queue: remove node, decrement neighbor indegrees.
4. If neighbor indegree becomes 0, push to queue.
5. If processed count != total nodes, there is a cycle.

#include <vector>
#include <queue>

bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
    std::vector<std::vector<int>> adj(numCourses);
    std::vector<int> indegree(numCourses, 0);

    // Build Graph
    for (const auto& pair : prerequisites) {
        // pair[0] depends on pair[1] -> edge: pair[1] -> pair[0]
        adj[pair[1]].push_back(pair[0]);
        indegree[pair[0]]++;
    }

    std::queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0) q.push(i);
    }

    int processedCount = 0;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        processedCount++;

        for (int neighbor : adj[curr]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    return processedCount == numCourses;
}

---

5. Rotting Oranges (Multi-Source BFS)

Problem: Minimum time to rot all oranges. 0=empty, 1=fresh, 2=rotten.

Concept: Start BFS from all rotten oranges simultaneously.

#include <vector>
#include <queue>

int orangesRotting(std::vector<std::vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    std::queue<std::pair<int, int>> q;
    int freshCount = 0;

    // 1. Initialize Queue with all rotten oranges
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == 2) {
                q.push({r, c});
            } else if (grid[r][c] == 1) {
                freshCount++;
            }
        }
    }

    if (freshCount == 0) return 0;

    int minutes = 0;
    std::vector<std::pair<int, int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};

    // 2. BFS Level by Level
    while (!q.empty()) {
        int size = q.size();
        bool rottedAny = false;

        for (int i = 0; i < size; ++i) {
            auto curr = q.front();
            q.pop();
            int r = curr.first;
            int c = curr.second;

            for (auto d : dirs) {
                int nr = r + d.first;
                int nc = c + d.second;

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2; // Rot it
                    q.push({nr, nc});
                    freshCount--;
                    rottedAny = true;
                }
            }
        }
        if (rottedAny) minutes++;
    }

    return freshCount == 0 ? minutes : -1;
}

Summary of Graph Patterns

Algorithm	Data Structure	Complexity	Use Case
DFS	Recursion / Stack	O(V+E)	Islands, Connectivity, Deep paths.
BFS	Queue	O(V+E)	Shortest Path (Unweighted), Level Order.
Topological Sort	Array (Indegree) + Queue	O(V+E)	Dependencies, Build Order, Cycle Detection.
Union Find (DSU)	Array (Parent)	O(E \alpha(V))	Dynamic Connectivity, Merging Sets (Kruskal's).
Dijkstra	Priority Queue	O(E \log V)	Shortest Path (Weighted, Non-negative).