图形内存实现

Question

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

Answer 1

链接相邻的向量是一个最喜欢的教科书meme与实践中的许多变化。当然你可以使用矢量向量。有什么区别？

其中之一就是链接（无论如何都是双重链接）允许在常量时间内容易地添加和删除边缘。这显然是重要的，只有边缘集缩小和增长。对于边缘矢量，任何单独的操作都可能需要O（k），其中k是入射边缘计数。

注意：如果邻接列表中的边缘的命令对您的应用程序不重要，您可以很容易地获取带有向量的O（1）删除。只需将最后一个元素复制到要删除的元素的位置，然后删除最后一个！唉，有很多情况下（比如你担心嵌入飞机的时候），当邻接点的顺序很重要时。

即使必须维护订单，您也可以安排复制成本以分摊到平均值O（1），以便在许多操作中执行每次操作。在某些应用中，这还不够好，只有当标记删除的数量是矢量的一个固定分数时，才需要“删除”标记（保留的顶点编号就足够了），并进行压缩。代码非常繁琐，在所有操作中检查已删除的节点会增加开销。

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

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

在大多数应用中，差异不值得担心。再次，巨大的图是现代世界的方式。

正如其他人所说的那样，为邻接点使用一个广义列表容器是一个好主意，它可以快速实现或者链接节点或节点向量。例如。在Java中，您可以使用List并使用LinkedList和ArrayList来实现/配置文件，以查看哪种最适合您的应用程序。 NB ArrayList压缩每个remove上的阵列。如上所述，并无摊销，尽管add s 为摊销。

还有其他的变化：假设你有一个非常密集的图，那里经常需要搜索所有出现在给定节点的边，以找出具有特定标签的边。那么你想要地图的邻接关系，其中的关键是边缘标签。当然，地图可以是哈希或树木或跳过列表或任何你喜欢的东西。

这个名单还在继续。如何实现高效顶点删除？正如您所预料的那样，这里也有其他选择，各有优缺点。