要实现图形，我们可以使用列表向量，std::vector<std::list<vertex>>
但我在某处看到如果使用这样的地图，std::map<vertex, std::set<vertex>>那么我们可以做得更好。任何人都可以弄清楚这在内存或速度方面比第一个更好的选择吗？
问问题
3148 次
1 回答
1
这里有两个不同之处需要注意。
std::vector<std::list<vertex>>是所谓的“邻接列表”，并且std::map<vertex, std::set<vertex>>被称为“邻接集”，不同之处在于使用 amap而不是 a对顶点数组索引进行散列vector。我将首先讨论第一个区别（即list<vertex>vs set<vertex>）。
第一个实现基本上是一个链表数组，其中每个链表给出与一个顶点相邻的所有顶点。第二种实现是将每个顶点映射到一组相邻顶点的有序映射。
邻接列表与邻接集增长顺序的比较：
空间：（E + V）与（E + V）
添加边：1 vs log V
检查邻接：（检查的顶点度数）vs log V
遍历顶点的邻居：（检查的顶点度数）vs（log V +检查的顶点度数）
... 其中 E 是边数，V 是顶点数，顶点的度数是连接到它的边数。（我使用的是无向图的语言，但你可以对有向图进行类似的推理）。因此，如果您有一个非常密集的图（每个顶点都有很多边，即高度），那么您想使用邻接集。
关于map vs vector的使用：插入和擦除对于vector来说是O(N)，对于map来说是O(log N)。然而，对于向量的查找是 O(1)，对于映射是 O(log N)。根据您的目的，您可能会使用其中一个。尽管您应该注意，当您使用连续的内存空间（如向量）时，会有缓存优化等。但是，我对此了解不多，但还有其他答案提到它：矢量或地图，使用哪一个？
于 2016-11-19T17:12:28.617 回答