c++ - 使用 boost 实现带有 vector 的图形

Question

我正在尝试使用 boost 和三个独立的 vector 来实现图形:

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

边缘定义为:

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

我的图表定义为:

typedef adjacency_list<vecS, vecS, undirectedS> Graph;

数组中全部填充了我从输入文件中获得的数据，因此顶点 vector 中的第一个元素类似于“A”，边 vector 中的第一个元素类似于 (B, C)并且权重 vector 中的第一个元素将是边 vector 中第一条边的权重，或者在这种情况下为 B-C。

问题是，我的 C++ 不是很流利，而且我也是 boost 和图形的新手。我试过查看 boost 网站上的示例代码，但它们都使用数组而不是 vector 。我试过这个示例代码:

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

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

有谁知道如何创建一个包含边、顶点和权重 vector 的图，我最终可以使用 Dijkstra 的 boost 版本？

抱歉，如果这个问题真的很模糊或很初级，我真的对使用 boost 和实现图形一无所知。

Answer 1

来自docs :

The type Graph must be a model of Vertex List Graph and Incidence Graph.

有 an example too 使用 adjacency_list 图。

当您在该示例中将 listS 替换为 vecS 时，将返回完全相同的响应(尽管我没有检查所有代码以确保此更改的完整性)

---

typedef adjacency_list<vecS, vecS, undirectedS> Graph;

从这一行来看，边上似乎没有weight 属性。在没有这些信息的情况下，Dijkstra 选择最佳路径会很困惑。快速浏览一下文档，我认为您可以提供一个外部 weight map 。另请注意:

Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one.