boost - 压缩稀疏行矩阵与邻接表

Question

Boost docs for compressed sparse row graph提及:

...CSR graphs have much less overhead than many other graph formats (e.g., adjacency_list)...

与邻接表相比，CSR 在开销方面究竟有何改进？两者都需要 O(|V| + |E|) 内存来存储图形。我认为边存在操作的时间复杂度也是一样的。

这个开销指的是什么？

编辑:经过一番思考，我觉得这可能是因为矩阵的每一行中的每个元素都存储在连续的内存位置？

Answer 1

区别在于常数和局部性。

请记住，O(n) 可能是 n、2*n 或固定 C，任何 C*n :)

存储在连续的内存区域中，在算法执行期间不太可能需要获取数据。这可以通过另一个常数 boost 算法的速度。