图表表示:邻接列表与矩阵

Question

我正准备进行编码面试,并且在图表上让我耳目一新.我想知道以下内容:在我看过的所有地方,假设邻接列表比大型稀疏图的邻接矩阵更有内存效率,因此在这种情况下应该是首选.此外,计算来自节点的输出边缘的数量需要矩阵中的O(N),而列表中的O(1),以及列表中的O(num相邻节点)中的相邻节点而不是O(N)表示矩阵.
这些地方包括Cormen等人的书,或StackOverFlow:使用邻接列表与邻接矩阵的图的大小？或维基百科.

但是,使用与压缩行存储表示相似的稀疏矩阵表示,内存要求仅为O(非零数)= O(边数),这与使用列表相同.来自节点的输出边缘的数量是O(1)(它直接存储在CRS中),并且相邻节点可以列在O(num相邻节点)中.
为什么不讨论它？我是否应该假设CSR 是由矩阵表示的图形的一种邻接列表表示？或者是矩阵存储器密集缺陷的论点,因为它们不考虑稀疏矩阵表示？

谢谢!

Answer 1

不是每个人每天都使用稀疏矩阵表示(我恰好这样做:),所以我猜没有人想到它们.它们是邻接列表和邻接矩阵之间的中间类型,如果选择正确的表示,其性能与第一个相似,并且对于某些图算法非常方便.

例如,要获得两个跳跃的接近矩阵,您只需将矩阵平方.我用适当的CPU时间用维基百科链接结构的稀疏矩阵表示成功完成了这个.