data-structures - 稀疏图和密集图有什么区别？

Question

我读到用邻接表表示稀疏图和用邻接矩阵表示密集图是理想的。但我想了解稀疏图和密集图之间的主要区别。

Answer 1

密集图是边数接近最大边数的图。 稀疏图是边数接近最小边数的图。稀疏图可以是断开的图。

Answer 2

正如名称所示，稀疏图是稀疏连接的（例如：树）。通常边的数量在 O(n) 中，其中 n 是顶点的数量。因此邻接表是首选，因为它们需要为每条边提供恒定的空间。

密集图是密集连接的。这里的边数通常是 O(n^2)。因此邻接矩阵是首选。

为了进行比较，我们假设图有 1000 个顶点。

无论图是密集的还是稀疏的，邻接矩阵都需要存储 1000^2 = 1,000,000 个值。

如果图是最小连接的（即它是一棵树），则邻接表需要存储 2,997 个值。如果图是全连接的，则需要存储 3,000,000 个值。

Answer 3

来自C++ 中具有面向对象设计模式的数据结构和算法，p。534，布鲁诺·赖斯（Bruno P. Reiss）：

通俗地说，边相对较少的图是稀疏的，边多的图是密集的。

定义（稀疏图）：稀疏图是一个图 G = (V, E)，其中 |E| = O(|V|)。

定义（密集图） 密集图是一个图 G = (V, E)，其中 |E| = Θ(|V| ² )。

Answer 4

图的主要积分特征是顶点数 V 和边数 E。这两者的关系决定了图是稀疏的还是密集的（此处为 wiki 页面）。

选择内存中图形表示背后的整个理论是关于确定最佳访问时间与内存占用的权衡，考虑主题域和使用细节。

通常，您希望拥有 O(1) 访问时间（从而将图形存储为密集邻接矩阵），除非您不能容忍内存占用，在这种情况下，您选择最合适的稀疏矩阵表示（此处的 wiki 页面）。

Answer 5

在数学中，稠密图是边数接近最大边数的图。相反，只有几条边的图是稀疏图。稀疏图和密集图之间的区别相当模糊，并且取决于上下文。

Answer 6

稀疏图 - 边缘相对较少的图（通常如果边缘 < |V| log |V|）称为稀疏图。密集图 - 可能缺失的边相对较少的图（与完整图相比）称为密集图。