稀疏图和密集图之间的区别是什么？

Question

我正在阅读如何在计算机内存中表示图形。我认为它是理想的用邻接矩阵表示邻接表和稠密图的稀疏图。但我想了解稀疏图和密集图的主要区别？

Answer 1

密集图是一个图中的边数接近最大边数。 稀疏图形是一个图形，其中边缘的数量接近边缘的最小数量。稀疏图可以是disconnected graph。

Answer 2

从here：

非正式地，用相对少的条边的图是稀疏的，并且与许多边的图是致密的。定义（稀疏图）：稀疏图是G =（V，E）的图，其中| E | = O（| V |）。定义（稠密图）稠密图是G =（V，E）的图，其中| E | =Θ（| V | ）。

Answer 3

主要图形积分特征是顶点数V和边数E.这两个关系决定图形是稀疏还是密集（维基页面here）。

选择图表内存表示的全部理论是关于确定最佳访问时间与内存占用情况的权衡，考虑主题领域和使用细节。

除非不能容忍内存占用，否则通常需要O（1）访问时间（并因此将图存储为密集的邻接矩阵），在这种情况下，您可以选择最合适的稀疏矩阵表示here）。

Answer 4

由于名称表示稀疏图是稀疏连接（例如：树）。通常边的数量在O（n）中，其中n是顶点的数量。因此，邻接列表是优选的，因为它们需要每个边缘的恒定空间。

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

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

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

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

Answer 5

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