如何从Boost Graph Library邻接表提取原始指针适配外部库？

对于你使用的boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>类型，无法直接提取到外部库所需的原始连续数组指针——原因是Boost的这个邻接表实现中，每个顶点的邻接顶点存储在独立的std::vector中，这些向量在内存中并非连续排布，因此不存在一个单一的连续数组可以直接作为adjncy参数传入。同样，xadj（CSR格式的行偏移数组）也需要手动构建，Boost并未直接暴露该结构。

你需要手动将邻接表转换为外部库要求的CSR格式，具体步骤如下：

1. 获取顶点数

   int num_nodes = static_cast<int>(boost::num_vertices(graph));
   

2. 构建行偏移数组xadj

   std::vector<int> xadj(num_nodes + 1, 0);
   for (int v = 0; v < num_nodes; ++v) {
       xadj[v+1] = xadj[v] + static_cast<int>(boost::out_degree(v, graph));
   }
   

3. 构建邻接顶点数组adjncy

   std::vector<int> adjncy;
   adjncy.reserve(xadj.back()); // 预分配足够空间，避免多次扩容
   for (int v = 0; v < num_nodes; ++v) {
       auto neighbors = boost::adjacent_vertices(v, graph);
       adjncy.insert(adjncy.end(), neighbors.first, neighbors.second);
   }
   

4. 调用外部库
   此时可以直接用向量的data()方法获取指针：

   external_library(num_nodes, xadj.data(), adjncy.data());
   

需要注意的是，因为你的图是无向图，Boost的adjacency_list会在邻接表中为每条无向边存储两个方向的条目（即添加边u-v后，u的邻接表包含v，v的邻接表包含u），这和大多数外部库对无向图CSR格式的要求一致，无需额外处理。

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