图的表示法：邻接表与矩阵

Question

图的表示法：邻接表与矩阵

11

我正在为编码面试做准备，并在复习图形知识。我想知道以下内容：在我所见的所有地方中，都认为邻接表比邻接矩阵更适用于大型稀疏图形，因此在这种情况下应该优先使用邻接表。此外，从节点计算出度需要O（N）的矩阵，而在列表中仅需O（1），对于相邻节点，列表只需要O（num adjacent nodes），而矩阵需要O（N）。这些地方包括Cormen等人的书籍，StackOverFlow：使用邻接表与邻接矩阵的图形大小？或维基百科。

然而，使用像压缩行存储表示的稀疏矩阵表示法，内存要求仅为O（number of non-zeros）= O（number of edges），与使用列表相同。节点的出度数为O（1）（直接存储在CRS中），并且可以在O（num adjacent nodes）中列出相邻节点。
为什么没有讨论它呢？我应该假设CSR是由矩阵表示的图的一种邻接表表示吗？还是说矩阵占用内存的论点是有缺陷的，因为它们没有考虑稀疏矩阵表示法？

谢谢！

- nbonneel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fred Foo · Accepted Answer

不是每个人每天都使用稀疏矩阵表示法（我碰巧使用:），所以我想没有人考虑过它们。它们是邻接表和邻接矩阵之间的一种中间形式，如果选择正确的表示方法，性能类似于第一个，并且对于某些图形算法非常方便。

例如，要获得两跳的近邻矩阵，您只需平方矩阵即可。我已经成功地使用稀疏矩阵表示法在适度的CPU时间内处理了维基百科链接结构。