C++图的邻接表表示法

Question

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

1. vector *edges; 2. list *edges; 3. map *edges; 4. map> edges;

在我看来，选项3或4应该是最好的选择，但我没有找到使用它们有任何不利之处...有吗？

请问有人可以帮我确定在竞赛编程中实现邻接表的最有效方法吗？

- Smile001

---

我建议使用 vector<vector<int>> adj_list。例如，adj_list[1] 将表示与顶点1共享边缘的所有顶点。 - Aditya_U

@Aditya_U，选项3或4有什么问题吗？使用向量在搜索顶点u和v之间是否存在边时需要O(n)的时间，但使用映射数据结构可以在很短的时间内完成。如果我执行edges[u]，我将获得u的所有相邻顶点的映射，并且可以高效地执行操作...你对此有什么看法？ - Smile001

Answer 1

如何在C++中实现图的邻接表表示的高效方法

许多典型的图形问题适用于给定的静态图形，需要先进行表示，之后可以在解决相关问题时重复使用该表示。在这种情况下，std::unordered_map<int, std::vector<int>>是一种合适的数据结构；在无序映射中，给定键的值表示给定顶点的（单向/双向）连接顶点。没有理由使用有序std::map来代替平均常数时间查找容器std::unordered_map。

关联容器std::unordered_map和std::unordered_set对查找很快（这是您想要的），但如果需要经常变异（例如，对于动态图问题），则可能会影响性能。像往常一样，针对实际问题实现进行剖析和测量运行时间和内存以查找瓶颈非常关键，特别是在实现高性能计算程序时。

- dfrib

---

我现在编辑的第四个选项怎么样？与其使用向量，我将再次使用映射来减少搜索时间... - Smile001

如果我考虑到所有操作的性能，使用向量相比于映射有什么优势？ - Smile001

Answer 2

这是特别针对您的第四个选项。

您可以从Sedgewick和Wayne的《算法》第4版中获得灵感，并选择unordered_multiset的array/vector（仅在无权边的情况下相邻节点）或unordered_multimap（在加权边的情况下相邻节点和边）。在那本书中，他们使用Java并使用Bag数据结构，这是一个对象的无序集合，可以重复。

“外部”数据结构的选择也可以是unordered_map，正如@dfrib所建议的那样。正如他所说，需要根据自己的应用程序进行测量以做出决定。

- Hari