Boost Graph Library（BGL）简单使用示例及技术问题咨询

一、双向图与有向图的核心区别 #

除入边遍历支持外，两者还有这些差异：

• 遍历接口：双向图提供in_edges()直接获取顶点的所有入边；普通有向图无此接口，需借助reverse_graph包装才能遍历入边。
• 内存开销：双向图会为每条边维护正向和反向的关联信息，内存占用比同规模有向图更高。
• 操作灵活性：双向图在处理需要同时关注入度、出度的场景（如社交网络双向关注、路由算法反向路径）时更直接，无需额外处理。

二、是否需要MutableBidirectionalGraph？ #

如果你的场景需要：

1. 频繁删除顶点/边
2. 直接访问顶点的入边
   那么必须使用满足MutableBidirectionalGraph概念的图类型。最常用的是配置合适参数的adjacency_list，示例中会具体展示。

三、完整实现示例 #

以下代码满足所有需求，包含顶点存储、ID查找、顶点/边增删、边成本维护：

#include <boost/graph/adjacency_list.hpp>
#include <unordered_map>
#include <iostream>

// 定义顶点结构体（选择带成员变量ID的版本，便于后续查找）
struct Vertex
{
    double m_d;
    std::size_t m_id;
};

// 定义边的属性结构体，存储边成本
struct EdgeCost
{
    double cost;
};

// 配置BGL图类型：
// - vecS：顶点容器用vector（默认，支持快速随机访问）
// - bidirectionalS：双向图模式，支持入边遍历和双向操作
// - VertexProperty：顶点存储Vertex类型
// - EdgeProperty：边存储EdgeCost类型
// - allow_parallel_edgeS：允许平行边（根据需求可选）
using Graph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::bidirectionalS,
    Vertex,
    EdgeCost,
    boost::no_property, // 无图级别属性
    boost::listS // 边容器用list，支持高效删除操作
>;

// 顶点描述符类型
using VertexDesc = boost::graph_traits<Graph>::vertex_descriptor;
// 边描述符类型
using EdgeDesc = boost::graph_traits<Graph>::edge_descriptor;

int main()
{
    Graph g;
    // 维护顶点ID到顶点描述符的映射，方便快速查找
    std::unordered_map<std::size_t, VertexDesc> id_to_vertex;

    // --------------------------
    // 1. 添加顶点
    // --------------------------
    VertexDesc v1 = add_vertex(Vertex{0.0, 1}, g);
    id_to_vertex[1] = v1;
    VertexDesc v2 = add_vertex(Vertex{0.0, 2}, g);
    id_to_vertex[2] = v2;
    VertexDesc v3 = add_vertex(Vertex{0.0, 3}, g);
    id_to_vertex[3] = v3;

    // --------------------------
    // 2. 根据ID查找顶点并修改m_d
    // --------------------------
    std::size_t target_id = 2;
    if (id_to_vertex.count(target_id))
    {
        VertexDesc v = id_to_vertex[target_id];
        g[v].m_d = 10.5; // 修改顶点的m_d值
        std::cout << "顶点ID " << target_id << " 的m_d已修改为: " << g[v].m_d << std::endl;
    }

    // --------------------------
    // 3. 添加带成本的边
    // --------------------------
    // 添加v1到v2的边，成本为5.0
    auto [e1, added1] = add_edge(v1, v2, EdgeCost{5.0}, g);
    // 添加v2到v3的边，成本为3.0
    auto [e2, added2] = add_edge(v2, v3, EdgeCost{3.0}, g);

    // 打印边成本
    std::cout << "边v1->v2的成本: " << g[e1].cost << std::endl;
    std::cout << "边v2->v3的成本: " << g[e2].cost << std::endl;

    // --------------------------
    // 4. 删除顶点与边
    // --------------------------
    // 先删除关联的边（删除顶点前需手动清理关联边，否则会导致悬空引用）
    remove_edge(v1, v2, g);
    // 删除顶点v2
    remove_vertex(v2, g);
    id_to_vertex.erase(2); // 更新ID映射表

    // 验证删除结果
    std::cout << "删除顶点2后，图中顶点数量: " << num_vertices(g) << std::endl;

    return 0;
}

代码说明 #

• 顶点查找：通过std::unordered_map维护ID到顶点描述符的映射，实现O(1)时间复杂度的查找。如果你的Vertex是用id()成员函数的版本，只需在添加顶点时将v.m_id替换为v.id()即可。
• 边成本：通过自定义EdgeCost结构体作为边属性，直接存储每条边的成本，访问时通过边描述符获取。
• 可修改性：选择bidirectionalS图类型和listS边容器，满足MutableBidirectionalGraph概念，支持边和顶点的删除操作。

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