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

Question

我读到它是理想的通过邻接列表表示稀疏图形和通过邻接矩阵表示密集图形.但我想了解稀疏图和密集图之间的主要区别.

Answer 1

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

Answer 2

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

密集的图形密集连接.这里边缘的数量通常是O(n ^ 2).因此,邻接矩阵是优选的.

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

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

如果图形是最小连接的(即它是树),则邻接列表需要存储2,997个值.如果图形完全连接,则需要存储3,000,000个值.

Answer 3

从这里:

非正式地,具有相对较少边缘的图是稀疏的,并且具有许多边的图是密集的.

定义(稀疏图):稀疏图是图G =(V,E),其中| E | = O(| V |).

定义(密集图)密集图是图G =(V,E),其中| E | =Θ(| V | ²).