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

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)依赖于使用情况,如你有什么用图形更经常这样做的:添加/删除顶点/边,只是穿越.一旦你的图形被创建,对Dijkstra一样std::list或者std::vector同样好,std::vector由于松弛阶段的顺序访问模式,速度要快一些.