图形内存实现

Question

常用的两种图形内存表示方法是使用邻接表或邻接矩阵。 邻接表使用指向链表的指针数组来实现。 使用指向向量的向量是否比使用邻接表更快？ 我认为这应该可以使搜索和遍历更快，因为回溯会更简单。

- user1874166

---

你只会一次回溯一个节点，对吗？那么双向链表也是同样好的选择。 - Karthik T

但这仍然需要额外的指针。因此，就内存和速度而言，向量是否仍然更好？ - user1874166

通常情况下，这取决于你的图是稀疏还是密集的。 - Kerrek SB

@KerrekSB 是的，我正在考虑这个，并且现在这甚至不一定是正确的。顺便说一下，我会使用哈希+向量或哈希+哈希组合来进行快速访问。 - Barney Szabolcs

如果您有数百万个顶点，但仅有少数几个边，邻接矩阵的内存非本地性将不值得使用......这真的取决于情况。最好让您的系统模块化，以便可以测试两种实现并进行比较。 - Kerrek SB

Answer 1

链接邻接向量是一种常见的教科书模式，在实践中有许多变化。当然，您可以使用向量的向量。它们之间有什么区别？

其中一个区别是，链接（双重链接）允许在常数时间内轻松添加和删除边缘。这显然只在边缘集合收缩和增长时很重要。对于边缘的向量，任何单个操作可能需要O(k)，其中k是关联边缘计数。

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

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

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

最后，经常在长时间内编辑的链接数据结构可能会导致高度不连续的内存访问。这会降低缓存性能，与通过向量进行线性访问相比。所以这里向量胜出。

在大多数应用程序中，这种差异不值得担心。再说，巨大的图形是现代世界的趋势。

正如其他人所说，使用通用的列表容器来处理邻接点是一个好主意，可以快速地使用链接节点或节点向量进行实现/分析。例如，在Java中，您可以使用List并使用LinkedList和ArrayList进行实现/分析，以查看哪种方法最适合您的应用程序。注意：ArrayList在每次remove时都会压缩数组。虽然上面描述了摊销，但add确实是摊销的。

还有其他变化：假设您有一个非常密集的图，需要频繁搜索与给定节点相邻的所有边以找到具有特定标签的边。然后，您需要使用邻接映射，其中键是边缘标签。当然，这些映射可以是哈希、树或跳表等任何您喜欢的东西。

列表还在继续。如何实现有效的顶点删除？正如您所预期的那样，这里也有不同的选择，每种选择都有其优缺点。

- Gene