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

EN

Dense graph是一个边数接近最大边数的图。稀疏图是一个边数接近最小边数的图。稀疏图可以是。

顾名思义，稀疏图是稀疏连接的(例如:树)。通常，边的数量是O(n)，其中n是顶点的数量。因此，邻接列表是首选的，因为它们需要每条边的恒定空间。

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

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

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

如果图是最小连通度(即，它是一棵树)，则邻接表需要存储2997个值。如果图是完全连接的，则需要存储3,000,000个值。

图的整体特征主要是顶点数V和边数E，这两者的关系决定了图是稀疏的还是稠密的(维基页面here)。

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

通常，您希望有O(1)个访问时间(并因此将图存储为密集邻接矩阵)，除非您不能容忍内存占用，在这种情况下，您选择最合适的稀疏矩阵表示(维基页面here)。