密集和稀疏运行时间

Question

我想制作一个程序，它可以在图形中找到最短路径。例如，我制作100个顶点和100个边，然后再制作100个顶点和500个边，并测量它们的运行时间。

我的问题是我该如何理解这是密集还是稀疏？

Answer 1

密度是图中边数与具有相同顶点集的完整图中边数的比值。

这两个图都相当稀疏，尽管第一个图比较稀疏。

通常的曲线图的密度用于决定使用什么样的数据结构来表示的曲线图

• 一种adjacency matrix使得用于密集图形感其中列举出边缘是​​不常见的操作。
• Edge lists对于稀疏图或经常进行枚举出站边缘有意义。

虽然这是一个折衷。随着顶点数的增加，邻接图占用更多的内存，但获取两个顶点之间边的列表很快。扫描所有外出边缘速度很慢。

随着顶点数量增加，边缘列表占用较少的内存，查找两个顶点之间的边更慢，但枚举出边更快。

Answer 2

不幸的是，“密集”和“稀疏”不容易适用于单个图形。通常情况下，稀疏图的边缘密度为o（n^2），密度图的边缘密度不是o（n^2）。但是，这不能应用于单个图表，而只是一个大小增长到无限大的图表族。你可以使用的“启发式”是：如果我在n个顶点（或n个顶点上的一族图）上有一个图，我有c * n个边（c是一个常数，相对较小），例如2n边缘，或3n边缘，或7n边缘？如果是，那么你有一个稀疏的图。否则，我有类似1/2 n^2边缘的东西吗？或1/3 n^2边缘？或1/10 n^2边缘？如果是的话，它很密集。

在您的示例中，100个顶点和500个边相当稀疏，因为5 * n个边看起来比1/200 n^2更“合理”。