BFS (Breadth-First Search)

Breadth-First Search is a graph traversal algorithm that explores all nodes at the current depth level before moving to the next level. It uses a queue to keep track of nodes to visit, ensuring a level-by-level traversal.

bfs.mov

BFS Implementation

vector<int> bfsOfGraph(vector<vector<int>> &adj) {  
    int n = adj.size();  
    queue<int> q;  
    vector<bool> visited(n, 0);  
    vector<int> bfs;  

    q.push(0);  
    visited[0] = 1;  

    while (!q.empty()) {  
        int node = q.front();  
        q.pop();  
        bfs.push_back(node);  

        for (auto ele : adj[node]) {  
            if (!visited[ele]) {  
                q.push(ele);  
                visited[ele] = 1;  
            }  
        }  
    }  

    return bfs;  
}

DFS (Depth-First Search)

Depth-First Search is a graph traversal algorithm that explores as far as possible along a branch before backtracking. It uses either:

• A stack (iterative implementation)
• Recursion (implicitly uses the call stack)

dfs.mov

private:
    void dfsCheck(int node, vector<int> &visited, vector<int> &dfs, vector<vector<int>>& adj){
        visited[node] = 1;
        dfs.push_back(node);
        
        for(auto ele: adj[node]){
            if(!visited[ele]){
                dfsCheck(ele, visited, dfs, adj);
            }
        }
    }
  public:
    vector<int> dfsOfGraph(vector<vector<int>>& adj) {
       
       int n = adj.size();
       vector<int> dfs;
       vector<int> visited(n,0);
       
       int start = 0;
       visited[0] = 1;
       dfsCheck(start, visited, dfs, adj);
       return dfs;
    }