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

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

标签： c++algorithmgraphdepth-first-searchbreadth-first-search

Answer 1

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

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

DFS 
2 
BFS
0  2  1  3 

建议：定义一个函数init()函数并在执行之前调用它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;
}

输出：

DFS 
2 3 1 0 
BFS
0  2  1  3