如何在权重邻接列表图上实现深度优先搜索？

Question

我正在对邻接列表中的加权图进行深度优先搜索。我知道技术上的加权在这里不会产生影响，但它会影响我的向量的设置方式，而且我不确定如何继续。我相信当我执行基于范围的 for 循环时它会失败，因为我的 adjListWeighted 包含第二个嵌入向量中的对，并且我不确定如何调整我的函数来纠正这一点。任何建议将不胜感激。

#include <vector>
#include <utility>
int main()
{
    std::vector<std::vector<std::pair<int, int>>> adjListWeighted(1);
    adjListWeighted[0].push_back({1, 5});
    for (int i : adjListWeighted[0]) {
    }
}

这是我从编译器收到的错误： 错误：无法在初始化中将 'std::pair' 转换为 'int'

Answer 1

不确定你到底在问什么，但是

for (int i : adjListWeighted[0]) {
    ...
}

将不起作用（即使 adjListWeighted 有内容），因为它是整数对的向量而不是整数。您需要范围元素变量是一对，或者需要使用结构化绑定来分配给两个整数变量。

我在下面做后者：

#include <vector>
#include <stack>
#include <unordered_set>
#include <iostream>

using weighted_edge = std::pair<int, int>;
using weighted_graph = std::vector<std::vector<weighted_edge>>;

void dfs(int start, const weighted_graph& g) {
    std::unordered_set<int> visited;
    std::stack<weighted_edge> stack;
    stack.emplace(start, 0);

    while (!stack.empty()) {
        auto [vert, weight] = stack.top();
        stack.pop();

        if (visited.contains(vert)) {
            continue;
        }
        visited.insert(vert);

        // do something with vert and/or weight...
        std::cout << vert << " : " << weight << "\n";

        for (const auto& edge : g.at(vert)) {
            stack.push(edge);
        }

    }
}

int main() {
    weighted_graph graph = {
        {{1,3},{2,3}},
        {{3,5},{2,4}},
        {{3,5}},
        {}
    };
    dfs(0, graph);
    return 0;
}