c++ - 图内存实现

Question

在内存中表示图形的两种常用方法是使用邻接表或邻接矩阵。邻接表是使用指向链表的指针数组实现的。有什么理由比使用 vector 的 vector 更快吗？我觉得它应该使搜索和遍历更快，因为回溯会简单得多。

Answer 1

邻接 vector 是最喜欢的教科书模因，在实践中有很多变化。当然你可以使用 vector 的 vector 。有什么区别？

一个是链接(无论如何都是双链接)允许在恒定时间内轻松添加和删除边。这显然只有在边集既收缩又增长时才重要。对于边 vector ，任何单独的操作都可能需要 O(k)，其中 k 是入射边数。

注意:如果邻接列表中边的顺序对您的应用程序不重要，您可以轻松地使用 vector 进行 O(1) 删除。只需将最后一个元素复制到要删除的位置，然后删除最后一个! las，在很多情况下(例如，您担心嵌入到平面中)邻接顺序很重要。

即使必须维持秩序，您也可以安排复制成本以平均分摊到许多操作中每个操作的 O(1)。在某些应用程序中，这仍然不够好，它需要“删除”标记(保留的顶点数就足够了)，只有当标记删除的数量是 vector 的固定分数时才执行压缩。代码很乏味，并且在所有操作中检查已删除的节点会增加开销。

另一个区别是开销空间。邻接表节点非常小:只是一个节点号。双链接可能需要数字本身空间的 4 倍(如果数字是 32 位并且两个指针都是 64)。对于非常大的图，400% 的空间开销不太好。

最后，长期频繁编辑的链接数据结构很容易导致高度不连续的内存访问。与通过 vector 进行线性访问相比，这会降低缓存性能。所以这里 vector 获胜。

在大多数应用程序中，差异并不值得担心。话又说回来，巨大的图表是现代世界的方式。

正如其他人所说，为邻接使用通用列表容器是个好主意，它可以通过链接节点或节点 vector 快速实现。例如。在 Java 中，您将使用 List 并使用 LinkedList 和 ArrayList 来实现/配置文件，以查看哪个最适合您的应用程序。注意 ArrayList 在每次删除 时压缩数组。尽管 add 已摊销，但没有如上所述的摊销。

还有其他变体:假设您有一个非常密集的图，其中经常需要搜索与给定节点关联的所有边以寻找具有特定标签的边。然后你需要 maps 的邻接关系，其中键是边缘标签。当然， map 可以是散列、树或跳表或任何你喜欢的东西。

不胜枚举。如何实现高效的顶点删除？如您所料，这里也有替代方案，各有优缺点。