如何在带权邻接表图上实现DFS？解决类型转换编译错误

错误原因 #

编译器报错error: cannot convert 'std::pair<int, int>' to 'int' in initialization的本质是：adjListWeighted[0]是std::vector<std::pair<int, int>>类型，存储的是邻接节点+对应权重的键值对，而你用int类型的变量接收这些键值对，导致类型不匹配。

修正方案 #

根据你对节点和权重的需求，有几种调整方式：

1. 同时获取邻接节点和权重（带权图常用）

直接用std::pair<int, int>或auto接收每个边元素，再通过first/second访问节点和权重：

#include <vector>
#include <utility>
int main()
{
    std::vector<std::vector<std::pair<int, int>>> adjListWeighted(1);
    adjListWeighted[0].push_back({1, 5});
    
    // 用auto简化类型声明
    for (auto edge : adjListWeighted[0]) {
        int neighbor = edge.first;  // 获取邻接节点编号
        int weight = edge.second;   // 获取边的权重
        // 这里编写DFS逻辑，比如递归访问neighbor节点，同时可利用weight做相关处理
    }
}

如果你的编译器支持C++17及以上，用结构化绑定会更简洁：

for (auto [neighbor, weight] : adjListWeighted[0]) {
    // 直接使用neighbor和weight变量编写DFS逻辑
}

2. 仅获取邻接节点（若暂时不需要权重）

如果你的DFS当前只需要遍历节点，可直接提取pair的first成员：

for (auto& edge : adjListWeighted[0]) {
    int neighbor = edge.first;
    // 执行DFS节点访问逻辑
}

补充说明 #

带权图的DFS核心逻辑确实和无权图一致，只是邻接表多存储了权重信息。你只需要调整循环中对邻接表元素的访问方式，不需要修改DFS的递归/栈核心逻辑。

内容的提问来源于stack exchange，提问作者Christian Tallett