在 C++ 中实现图形的邻接表表示的有效方法是什么?
- 矢量*边;
- 列出*边;
- 地图<int, int> *edges;
- map<int, map<int, int>> 边;
在我看来,它应该是选项 3 或 4,但我找不到使用它的任何缺点......有吗?
有人可以帮助我,这将是实现邻接列表和竞争性编程的最有效方式吗?
在 C++ 中实现图形的邻接表表示的有效方法是什么?
在我看来,它应该是选项 3 或 4,但我找不到使用它的任何缺点......有吗?
有人可以帮助我,这将是实现邻接列表和竞争性编程的最有效方式吗?
什么是在 C++ 中实现图形的邻接表表示的有效方法
许多典型的图问题适用于给定的静态图,该图需要表示一次,然后在解决相关问题时可以重用给定的表示。在这种情况下,std::unordered_map<int, std::vector<int>>
是一个合适的结构;其中无序映射中给定键的值表示给定顶点的(单向/双向)连接顶点。应该没有理由在摊销的常数时间查找容器上使用排序。std::map
std::unordered_map
关联容器可以std::unordered_map
快速std::unordered_set
查找(您在此处需要),但如果它们需要经常变异(例如,对于动态图问题),可能会对性能产生影响。与往常一样,如果您要实现高性能计算程序,分析和测量运行时和内存以找到实际问题实现的瓶颈是关键。
这是为了特别解决您的第四个选项。
您可以从Sedgewick 和 Wayne的Algorithms, 4th Edition中获取灵感,并使用s 的array
/ (仅在未加权边的情况下为相邻节点)或s(在加权边的情况下为相邻节点和边)。在那本书中,他们使用 Java 并使用 Bag 数据结构,这是一个无序的对象集合,具有重复的可能性。vector
unordered_multiset
unordered_multimap
unordered_map
正如@dfrib 所建议的那样,“外部”数据结构的选择也可以。正如他所说,一个人需要衡量一个人的应用来决定。