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