java - 密集和稀疏运行时间

Question

我正在尝试编写一个程序来查找图中的最短路径。例如，我制作了 100 个顶点和 100 条边，然后又制作了 100 个顶点和 500 条边，并测量它们的运行时间。

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

Answer 1

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

这两个图都相当稀疏，但第一个更稀疏。

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

• 安 adjacency matrix对于枚举出站边缘不是常见操作的密集图很有意义。
• Edge lists对于稀疏图或经常枚举出站边缘的地方有意义。

不过这是一种权衡。随着顶点数的增加，邻接图会占用更多的内存，但是获取两个顶点之间的边列表很快。扫描所有出站边缘很慢。

随着顶点数的增加，边列表占用的内存更少，在两个顶点之间寻找边的速度变慢，但枚举传出边的速度很快。