Boost.Graph 入门指南（C++图算法与Boost库实战详解）

安装与配置

Boost 是一个纯头文件库（部分组件除外），因此大多数情况下你只需下载并包含头文件即可使用 Boost.Graph。以 Ubuntu 为例：

sudo apt-get install libboost-all-dev

在代码中，只需包含以下头文件：

#include <boost/graph/adjacency_list.hpp>#include <boost/graph/graph_traits.hpp>

创建一个简单图

我们使用 adjacency_list 来定义一个有向图。下面是一个完整示例：

#include <iostream>#include <boost/graph/adjacency_list.hpp>int main() {    // 定义图类型：有向图，使用 vecS 存储顶点，listS 存储邻接表    using Graph = boost::adjacency_list<        boost::vecS,           // OutEdgeList        boost::vecS,           // VertexList        boost::directedS       // Directed or undirected    >;    Graph g;    // 添加顶点    auto v0 = boost::add_vertex(g);    auto v1 = boost::add_vertex(g);    auto v2 = boost::add_vertex(g);    // 添加边：v0 → v1，v1 → v2    boost::add_edge(v0, v1, g);    boost::add_edge(v1, v2, g);    std::cout << "图中共有 " << boost::num_vertices(g) << " 个顶点\n";    std::cout << "图中共有 " << boost::num_edges(g) << " 条边\n";    return 0;}

遍历图中的顶点和边

Boost.Graph 提供了迭代器来遍历图：

// 遍历所有顶点boost::graph_traits<Graph>::vertex_iterator vi, vend;for (boost::tie(vi, vend) = boost::vertices(g); vi != vend; ++vi) {    std::cout << "顶点 ID: " << *vi << std::endl;}// 遍历所有边boost::graph_traits<Graph>::edge_iterator ei, eend;for (boost::tie(ei, eend) = boost::edges(g); ei != eend; ++ei) {    std::cout << "边: " << boost::source(*ei, g)               << " -> " << boost::target(*ei, g) << std::endl;}

常用图算法：最短路径

Boost.Graph 内置了多种经典算法，比如 Dijkstra 最短路径算法：

#include <boost/graph/dijkstra_shortest_paths.hpp>// 为边添加权重属性using Weight = boost::property<boost::edge_weight_t, int>;using WeightedGraph = boost::adjacency_list<    boost::vecS, boost::vecS, boost::directedS, boost::no_property, Weight>;WeightedGraph wg;auto w0 = boost::add_vertex(wg);auto w1 = boost::add_vertex(wg);auto w2 = boost::add_vertex(wg);boost::add_edge(w0, w1, 5, wg);boost::add_edge(w1, w2, 3, wg);boost::add_edge(w0, w2, 10, wg);std::vector<int> distances(boost::num_vertices(wg));boost::dijkstra_shortest_paths(wg, w0, boost::distance_map(&distances[0]));std::cout << "从顶点 0 到各点的最短距离：\n";for (size_t i = 0; i < distances.size(); ++i) {    std::cout << "到 " << i << " 的距离: " << distances[i] << std::endl;}

总结

通过本教程，你已经掌握了 Boost.Graph教程 的核心内容：如何创建图、添加顶点与边、遍历图结构，并运行经典图算法。无论你是想实现 C++图算法 还是进行 图数据结构C++ 的工程开发，Boost.Graph 都能提供强大而灵活的支持。

建议你动手尝试修改上述代码，添加更多顶点或尝试其他算法（如 BFS、DFS、最小生成树等），逐步提升你的 Boost库入门 技能！