c++ - 构建图形的最佳标准数据结构是什么？

Question

起初我是c++的初学者，我是自学的，所以请尽量简单的回答...

我需要编写一个包含节点的图，每个节点都有 id 和边列表，每个边都有另一个节点 id 和距离

考虑到我想使用 dijkstra 算法获得从一个点到另一个点的最短路径，我正在寻找的是我应该使用什么来构建这个图......所以我认为搜索性能应该是最重要的! !

我搜索了很多，现在我很困惑

提前感谢您的帮助

Answer 1

你可以像这样定义一个Edge结构

struct Edge
{
    int destination;
    int weight;
};

并创建一个图表作为

vector<vector<Edge> > graph;

然后要访问来自顶点 u 的所有边，您可以编写如下内容

for( int i = 0; i < graph[u].size(); ++i ) {
    Edge edge = graph[u][i];
    // here edge.destination and edge.weight give you some details.
}

您可以动态添加新边，例如从第 3 个顶点到第 7 个顶点的边，权重为 8:

Edge newEdge;
newEdge.destination = 7;
newEdge.weight = 8;
graph[3].push_back( newEdge );

等等

当然，对于无向图，您不应忘记添加对称边。

这应该没问题。

编辑基本容器(std::vector、std::list、std::map)的选择取决于用例，例如你更经常地用图做什么:添加/删除顶点/边，只是遍历。创建图形后，std::list 或 std::vector 对 Dijkstra 来说同样好，std::vector 有点由于松弛阶段的顺序访问模式，速度更快。