C++ 图的邻接表表示

Question

在 C++ 中实现图的邻接表表示的有效方法是什么？

1. 向量*边；
2. 列出*边；
3. 地图<int, int> *边缘;
4. 地图<int, 地图<int, int>> 边；

在我看来，应该是选项3或4，但我找不到使用它的任何缺点......有什么缺点吗？

有人可以帮助我，这将是实现邻接表和竞争性编程的最有效方法吗？

Answer 1

在 C++ 中实现图的邻接列表表示的有效方法是什么

许多典型的图问题适用于给定的静态图，需要将其表示一次，然后在解决相关问题时可以重新使用给定的表示。在这种情况下，std::unordered_map<int, std::vector<int>>是一个合适的结构；其中无序映射中给定键的值表示给定顶点的（单向/双向）连接顶点。没有理由在摊销常数时间查找容器上使用有序的。std::mapstd::unordered_map

关联容器std::unordered_map和std::unordered_set可以快速查找（您在这里想要的），但如果它们需要经常变化（例如对于动态图问题），可能会对性能产生影响。与往常一样，如果您正在实现高性能计算程序，那么分析和测量运行时和内存以找到实际问题实现的瓶颈是关键。