Iterative BFS

  • Despite its apparent simplicity, this approach relies heavily on the utilization of various STL containers.
  • std::unordered_map records the parent of each node
  • std::unordered_set checks if a node has been visited
  • std::queue allows the nodes be accessed in the width-first flow; using std::stack for depth-first flow
  • std::stack reverses the parents, so the path can be printed in root-to-target order.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>

std::stack<int> BFS(const int root, const int target, const std::vector<int>& rowPtr, const std::vector<int>& colIdx) {
   
    std::unordered_map<int, int> parent;
    std::unordered_set<int> visited;
    std::queue<int> nodeQue;  // std::stack<int> nodeStk for DFS
    std::stack<int> path;
    bool hasFound = false;

    nodeQue.push(root);
    visited.insert(root);

    while(!nodeQue.empty()) {
        auto curr = nodeQue.front();  // nodeStk.top() for DFS
        nodeQue.pop();

        if(curr == target) {
            hasFound = true;
            break;
        }

        for(int i = rowPtr[curr]; i < rowPtr[curr+1]; i++) {
            auto next = colIdx[i];
            if(visited.count(next) == 0)
            {   
                nodeQue.push(next);
                visited.insert(next);
                parent[next] = curr;
            }
        }
    }

    if(hasFound) {
        auto curr = target;
        path.push(curr);
        if(curr != root) {
            curr = parent[curr];
            path.push(curr);
        }
        path.push(root);
    } 
    return path;
}


int main() {
    std::vector<int> rowPointer = {0, 2, 4, 6, 8, 10, 12};
    std::vector<int> colIndices = {1, 2, 0, 3, 0, 1, 4, 1, 2, 5, 3, 5};

    auto path = BFS(0, 5, rowPointer, colIndices);

    if(path.empty()) {
        std::cout << "Path Not Found\n";
    } else {
        std::cout << "Path from Root to Target: ";
        while(!path.empty())  {
            std::cout << path.top() << ' ';
            path.pop();
        }
    }
    
    return 0;
}

Recursive DFS

  • DFS naturally aligns with recursion. In the earlier example, the iterative DFS employs the std::stack to facilitate the depth-first progression. On the other hand, recursion, which stores function calls in the stack memory, permits the execution of DFS functions in a last-in-first-out manner, eliminating the need for using std::stack.
  • Here, std::vector<bool> is utilized instead of std::unordered_set<int> for memory efficiency.
#include <iostream>
#include <vector>


void DFS(const int root, const int target, std::vector<int>& path, std::vector<bool>& visited, const std::vector<int>& rowPtr, const std::vector<int>& colIdx) {
   visited[root] = true;
   path.push_back(root);

   if(root == target) {
    std::cout << "DFS path from root to target: ";
    for(int i = 0; i < path.size(); i++) {
        std::cout << path[i] << " ";
    }
    std::cout << '\n';
   }    
   for(int i = rowPtr[root]; i < rowPtr[root+1]; i++) {
      int next = colIdx[i];
      if( visited[next] == false ) {
        DFS(next, target, path, visited, rowPtr, colIdx);
      }
    }
}


int main() {
    std::vector<int> rowPointer = {0, 2, 4, 6, 8, 10, 12};
    std::vector<int> colIndices = {1, 2, 0, 3, 0, 1, 4, 1, 2, 5, 3, 5};
    std::vector<int> path;
    std::vector<bool> visited( rowPointer.size()-1, false );  //used as unordered_set

    DFS(0, 5, path, visited, rowPointer, colIndices);
    
    return 0;
}