如何在C/C++中使用指针解决DFS实现中图大小恒为0的问题

你的代码核心问题是函数参数的值传递，导致修改的是实参的临时副本，原变量没有被改动，才会出现图大小始终为0的情况。 #

具体错误位置 #

• 第一个错误是addEdge函数的graph参数用了值传递：你在函数里修改的是传入的graph的临时副本，函数执行完副本就销毁了，main函数里的原graph完全没被改动，自然大小永远是0。这里需要把参数改成引用，或者用指针传递，才能修改原变量。
• 第二个优化点是dfs_recursive的graph参数也用了值传递：每次递归调用都会复制整个图，性能损耗极大，你不需要修改图的话用const引用就可以，避免不必要的拷贝。
• 额外的语法与逻辑问题：你定义bool visited[v]={false};的时候v是变量，C++标准不支持可变长度数组（VLA），这是部分编译器的扩展语法，最好改成动态分配或者用vector<bool>实现；另外你定义的v=4，但节点最大编号是4，数组长度为4的话下标最大为3，访问节点4会出现数组越界。

修正后完整代码 #

#include<iostream>
#include<vector>
#include<map>
using namespace std;

// graph参数改为const引用，避免拷贝，不需要修改图所以加const
void dfs_recursive(const map<int, vector<int>>& graph, bool visited[], int source){
    visited[source] = true;
    cout << source << " " << endl;
    cout << "graph size: " << graph.size() << endl;
    for(int i = 0; i < graph.at(source).size(); i++){
        int neighbor = graph.at(source)[i];
        cout << "i: " << i << endl;
        if(!visited[neighbor])
            dfs_recursive(graph, visited, neighbor);
    }
}

// graph参数改为引用，修改会作用到原变量
void addEdge(map<int, vector<int>>& graph, int source, int dest){
    graph[source].push_back(dest);
    graph[dest].push_back(source);
}

int main(){
    const int v = 5; // 节点最大是4，数组大小要设为5，避免访问下标4越界
    map<int, vector<int>> graph;
    bool visited[v] = {false}; // 完全符合C++标准的写法可替换为vector<bool> visited(v, false);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    dfs_recursive(graph, visited, 2);
    return 0;
}

补充说明 #

如果要用指针代替引用实现修改原变量，只需要把addEdge的参数改为map<int, vector<int>>* graph，调用函数时传入&graph，函数内部访问成员改为->即可，效果和引用完全一致。

内容的提问来源于stack exchange，提问作者Shreya Birthare