c++ - 图内存实现

Question

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

Answer 1

链接邻接向量是最受欢迎的教科书模因，在实践中有许多变化。当然，您可以使用向量的向量。有什么区别？

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

注意：如果邻接列表中边的顺序对您的应用程序不重要，您可以使用向量轻松获得 O(1) 删除。只需将最后一个元素复制到要删除的位置，然后删除最后一个！唉，当邻接顺序很重要时，有很多情况（例如，您担心嵌入平面中）。

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

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

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

在大多数应用程序中，这种差异并不值得担心。再说一次，巨大的图表是现代世界的方式。

正如其他人所说，对邻接使用通用列表容器是一个好主意，它可以通过链接节点或节点向量快速实现。例如，在 Java 中，您将List同时使用和实现/配置文件，LinkedList并ArrayList查看哪个最适合您的应用程序。NBArrayList在每个remove. 如上所述，没有摊销，尽管adds是摊销的。

还有其他变体：假设您有一个非常密集的图，其中经常需要搜索与给定节点相关的所有边以查找具有特定标签的边。然后你想要邻接的地图，其中键是边缘标签。当然地图可以是散列或树或跳过列表或任何你喜欢的。

名单还在继续。如何实现高效的顶点删除？正如您所料，这里也有替代方案，每个都有优点和缺点。