logo标签列表

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

data-structuresgraphgraph-theory
57

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

5
密集图是一个图论概念，指的是在一个无向图或有向图中，边数接近于完全图（完全图是指每个顶点都与其他所有顶点相连的图）。密集图通常具有许多边和相对较少的孤立节点。 - Imposter
8个回答
51

密图是指边数接近于最大可能边数的图。 稀疏图是指边数接近于最小可能边数的图。稀疏图可以是一个不连通的图。

2
我认为，如果一个有n个顶点的图具有O(n)或更少的边，则被认为是稀疏的。 - Gabor Csardi
2
相反地，如果一个图有n个顶点且边的数量为O(n^2)，则该图是密集的。 - JayJay
41
如名称所示，稀疏图很少相互连接（例如：树）。通常，边的数量为O(n)，其中n是顶点数。因此，优先使用邻接表，因为它们对于每条边都需要恒定的空间。
稠密图则连接密集。这里，边的数量通常为O(n²)。因此，邻接矩阵更受欢迎。
为了进行比较，假设图形具有1000个顶点。
无论图形是稠密还是稀疏，邻接矩阵需要存储1,000,000个值。
如果图形是最小连接的（即为树），则邻接列表需要存储2,997个值。如果图形完全相连，则需要存储3,000,000个值。
2
邻接表对于1000个顶点需要2997个值，您能详细说明一下吗？ - Surya Teja Vemparala
@SuryaTejaVemparala 这里将稀疏图视为一棵树。将树视为1-2-3-4-....-1000，对于从2到999的每个顶点，都会有两个条目，一个是前一个顶点，另一个是下一个顶点。第一个和最后一个只有一个条目，然后是邻接表中所有键的额外空间（如果通过哈希映射构建）。我认为如果使用列表的列表，可以将其减少到1998。 - lucifer
15
3
主图的积分特征是顶点数V和边数E。这两者之间的关系决定了图形是稀疏还是密集（维基页面在此）。
选择内存中表示图形的整个理论是关于确定最佳访问时间与内存占用的权衡，考虑主题域和使用特定的情况。
通常情况下，您希望具有O（1）访问时间（因此将图形存储为密集邻接矩阵），除非您无法容忍内存占用，此时您将选择最适合的稀疏矩阵表示（维基页面在此处）。
1

在数学中，稠密图是指边数接近最大边数的图。相反地，仅有少量边的图被称为稀疏图。稀疏图和稠密图之间的区别相当模糊，并取决于上下文。

稀疏图的几个例子包括： 交通和道路网络，其中交叉口是顶点，道路是边缘。对于这样的网络，道路数量不会显著大于交叉口数量（换句话说，E~=c * V，其中c在2-3范围内）。 虽然在许多情况下现实世界中的图形是稀疏的，但是可以创建高度密集的加权图形，其中边缘权重表示某种关系 - 例如，如果两个人同时在同一家商店或咖啡店喝咖啡，则具有大的边缘权重。 - Akash Kandpal
另一个例子可能是从表示高度连接的人群社区的稀疏图中取出一个“子图”。 - Akash Kandpal
1

enter image description here

在上面的答案中，更简单的解释可以是：

  • 稠密图 如果图中所有顶点或节点都密集连接（即一个节点与所有相邻节点连接具有所有可能的边缘）。在这里，可能的总边数>总节点数。

  • 稀疏图 它是稠密图的反义词，在这里我们可以观察到一个节点或顶点没有完全连接到其相邻节点（即它具有未连接/剩余的边缘）。在这里，可能的总边数<=总节点数。

1

如果一张图的边数接近于最大边数，那么这张图就是一个稠密图。在稠密图中，每对顶点之间都有一条边相连。

稀疏图则完全相反。如果一张图只有很少的边（边数接近最小值），那么它就是一个稀疏图。

稀疏图和稠密图之间没有严格的区分。通常情况下，一个稀疏（连通）图的边数与顶点数大致相等，而一个稠密图的边数接近于最大边数。

0
稀疏图 - 边相对较少的图（通常如果边数 < |V| log |V|）被称为稀疏图。 密集图 - 相对于完全图，缺少可能的边相对较少的图被称为密集图。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接