为什么我需要为 BFS 中的每个元素分配 false 而不是 DFS 中的

Question

函数定义为：

// 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 在不使用 for 循环分配访问数组的每个元素等于 false 的情况下工作正常，但 BFS 不是。为什么？整个程序代码是 - https://hastebin.com/ojuyogexof.cpp

Answer 1

在调用 DFS() 之前，访问过的数组从未初始化为 fasle，这就是为什么 DFS() 的输出只是单个节点（起始节点），即 2.

整个代码的输出（没有将访问数组初始化为 false）：

DFS 
2 
BFS
0  2  1  3

建议： 定义一个函数 init() 函数并在执行 DFS() 或 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;
}

输出：

DFS 
2 3 1 0 
BFS
0  2  1  3

为什么我需要为 BFS 中的每个元素分配 false 而不是 DFS 中的

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

c++

algorithm

graph

breadth-first-search

depth-first-search