Boost Graph Library中distance_recorder使用异常：BFS求节点距根距离错误

你的问题出在Boost Graph Library读取Graphviz dot文件时，顶点名称与图的顶点索引没有正确绑定，导致实际构建的图结构与你预期的完全二叉树不一致，最终BFS计算的距离结果错误。

具体原因 #

当你使用read_graphviz读取dot文件时，默认情况下，它会将dot中的顶点名称（如"0"、"1"）当作一个独立的name属性存储，而不是直接映射到图的vertex_index（顶点索引）。即使你的dot文件中顶点是按顺序列出的，也可能因为内部处理逻辑导致顶点索引与名称不匹配，或者边被错误地关联到错误的顶点上，进而让BFS遍历路径完全偏离预期。

修复步骤 #

1. 绑定顶点名称到顶点索引

修改你的dynamic_properties设置，明确将dot文件中的node_id（顶点名称）映射到图的vertex_index属性，确保顶点名称与索引一一对应：

boost::dynamic_properties dp{ boost::ignore_other_properties };
// 关键：将dot中的node_id绑定到图的vertex_index属性
dp.property("node_id", get(boost::vertex_index, g));
boost::read_graphviz(dot_file, g, dp);

2. 验证图的边结构（可选但推荐）

为了确认图的边是否正确，可以添加代码输出所有边，确保和dot文件中的结构一致：

std::cout << "Graph edges:\n";
for (auto e : boost::make_iterator_range(boost::edges(g))) {
    std::cout << boost::source(e, g) << " -> " << boost::target(e, g) << '\n';
}

运行后，你应该看到与dot文件一致的边：0->1、0->2、1->3等，这说明图结构正确。

3. 重新运行BFS

修改后的完整代码如下：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>
#include <fstream>

int main() {
    using DiGraph = boost::adjacency_list<>;
    DiGraph g;
    std::ifstream dot_file("graph.dot");
    if (!dot_file.is_open()) {
        std::cerr << "Failed to open graph.dot!\n";
        return 1;
    }

    boost::dynamic_properties dp{ boost::ignore_other_properties };
    // 绑定node_id到vertex_index，确保顶点名称与索引对应
    dp.property("node_id", get(boost::vertex_index, g));
    boost::read_graphviz(dot_file, g, dp);

    // 输出边验证结构（可选）
    std::cout << "Graph edges:\n";
    for (auto e : boost::make_iterator_range(boost::edges(g))) {
        std::cout << boost::source(e, g) << " -> " << boost::target(e, g) << '\n';
    }

    // 明确获取根节点（索引为0的顶点）
    auto vd0 = boost::vertex(0, g);
    using vertices_size_type = boost::graph_traits<DiGraph>::vertices_size_type;
    std::vector<vertices_size_type> distances(boost::num_vertices(g), 0); // 显式初始化为0
    auto dist_pmap = boost::make_iterator_property_map(
        distances.begin(), get(boost::vertex_index, g));
    auto vis = boost::make_bfs_visitor(
        boost::record_distances(dist_pmap, boost::on_tree_edge()));
    boost::breadth_first_search(g, vd0, visitor(vis));

    std::cout << "\nDistances to root:\n";
    for (auto v : boost::make_iterator_range(boost::vertices(g))) {
        std::cout << "d[0, " << v << "] = " << distances[v] << '\n';
    }

    return 0;
}

预期输出 #

修复后，运行代码应该得到正确的距离：

Graph edges:
0 -> 1
0 -> 2
1 -> 3
1 -> 4
2 -> 5
2 -> 6
3 -> 7
3 -> 8
4 -> 9
4 -> 10
5 -> 11
5 -> 12
6 -> 13
6 -> 14

Distances to root:
d[0, 0] = 0
d[0, 1] = 1
d[0, 2] = 1
d[0, 3] = 2
d[0, 4] = 2
d[0, 5] = 2
d[0, 6] = 2
d[0, 7] = 3
d[0, 8] = 3
d[0, 9] = 3
d[0, 10] = 3
d[0, 11] = 3
d[0, 12] = 3
d[0, 13] = 3
d[0, 14] = 3

额外说明 #

• 我们将获取根节点的方式从*boost::vertices(g).first改为boost::vertex(0, g)，这样更明确，确保我们获取的是索引为0的顶点，避免因顶点顺序问题导致错误。
• 显式将distances向量初始化为0，让代码逻辑更清晰（虽然默认初始化也是0）。

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