构建图的最佳标准数据结构是什么？

Question

起初我是 C++ 的初学者，我是自学的，所以请回答很简单……

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

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

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

提前感谢您的帮助

原文由 Dawnlight 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 由于松弛阶段的顺序访问模式而更快一些。

原文由 unkulunkulu 发布，翻译遵循 CC BY-SA 3.0 许可协议