首页 文章

使用boost实现带矢量的图形

提问于
浏览
1

我正在尝试使用具有三个单独向量的boost来实现图形:

std::vector<std::string> vertex_array;
std::vector<Edge> edge_array;
std::vector<int> weight_array;

Edge定义为:

typedef std::pair<std::string, std::string> Edge;

我的图表定义为:

typedef adjacency_list<vecS, vecS, undirectedS> Graph;

数组都填充了我从输入文件中获得的数据,因此顶点向量中的第一个元素将类似于“A”,边缘向量中的第一个元素将类似于(B,C)和第一个元素权重向量中的元素将是边缘向量中的第一个边缘的权重,或者在这种情况下是BC .

问题是,我对C语言不是很流利,而且我也很想提升和绘制图表 . 我试过在boost网站上查看示例代码,但它们都使用数组而不是向量 . 我确实试过这个示例代码:

Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);

我确实有一个num_vertices变量,但它仍然给我一个错误 .

有没有人知道如何使用边缘,顶点和权重矢量创建图形,我最终能够使用Dijkstra的增强版本?

很抱歉,如果这个问题非常模糊或基本,我真的不知道如何使用boost和实现图表 .

1 回答

  • 1

    来自docs

    Graph类型必须是Vertex List Graph和Incidence Graph的模型 .

    an example too 使用 adjacency_list 图表 .

    当您在该示例中将 listS 替换为 vecS 时,将返回完全相同的响应(虽然我没有检查所有代码是否具有此更改的完整性)


    typedef adjacency_list<vecS, vecS, undirectedS> Graph;
    

    从这一行看来,边缘上没有 weight 属性 . Dijkstra选择没有这些信息的最佳路径会让人感到困惑 . 从快速浏览一下文档,我认为你可以提供一个外部 weight Map . 另请注意:

    当所有边权重等于1时,使用广度优先搜索而不是Dijkstra算法 .

相关问题