Why do I need to assign false to each element in BFS but not in DFS

Question

Function definitions are :

// DFS algorithm
void Graph::DFS(int current) {


    visited[current] = true;
    cout<<current << " ";
        

    for (int u : adjLists[current])
        if (!visited[u])
            DFS(u);

}

// BFS algorithm

void Graph::BFS(void){
    
    for(int i=0;i<numVertices;++i)
        visited[i] = false;
        
    list<int> q;
    q.push_back(0);
    visited[0] = true;
    
    while(!q.empty())
    {
        int u = q.front();
        q.pop_front();
        cout<< u << "  ";
        
        for( int i : adjLists[u])
            if(!visited[i]){
                q.push_back(i);
                visited[i] = true;
            }   
    }
}

DFS is working fine without using for loop to assign each element of visited array equal to false but BFS is not. Why? Whole program code is - https://hastebin.com/ojuyogexof.cpp

Answer 1

The visited array never got initialised to fasle before calling the DFS() and that is why the output for the DFS() is only single node (starting node), i.e., 2.

Output for the entire code (without initialising visited array to false):

DFS 
2 
BFS
0  2  1  3 

SUGGESTION: Define a function init() function and call it before performing DFS() or BFS():

#include <bits/stdc++.h>
using namespace std;

class Graph {
    int numVertices;
    list<int> *adjLists;
    bool *visited;

    public:
    Graph(int V);
    void addEdge(int src, int dest);
    void DFS(int vertex);
    void BFS(void);
    void init();
};

// Initialize graph
Graph::Graph(int vertices) {
    numVertices = vertices;
    adjLists = new list<int>[vertices];
    visited = new bool[vertices];
    for(int i=0;i<numVertices;++i){
        visited[i] = false;
    }
}

void Graph::init() {
    for(int i=0;i<numVertices;++i)
        visited[i] = false;
}

// Add edges
void Graph::addEdge(int src, int dest) {
    adjLists[src].push_front(dest);
    adjLists[dest].push_front(src);
}

// DFS algorithm
void Graph::DFS(int current) {
        
    visited[current] = true;
    cout<<current << " ";
        
    for (int u : adjLists[current])
        if (!visited[u])
            DFS(u);

}

// BFS algorithm

void Graph::BFS(void){
    
    list<int> q;
    q.push_back(0);
    visited[0] = true;
    
    while(!q.empty())
    {
        int u = q.front();
        q.pop_front();
        cout<< u << "  ";
        
        for( int i : adjLists[u])
            if(!visited[i]){
                q.push_back(i);
                visited[i] = true;
            }    
    }
}

int main() {
    
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);


    g.init();
    int start_node = 2 ;
    cout<<"DFS \n";
    g.DFS(start_node) ;

    g.init();
    cout<<endl<<"BFS"<<endl;
    g.BFS();

    return 0;
}

Output:

DFS 
2 3 1 0 
BFS
0  2  1  3