图表示法：邻接表与矩阵 [英] graphs representation : adjacency list vs matrix
问题描述
我正准备进行一次编码采访，并用图表刷新了我的想法。我想知道以下几点：在我见过的所有地方，都假定邻接表比邻接矩阵更适合大型稀疏图，因此在这种情况下应该是首选。另外，计算一个节点的输出边的数量需要一个矩阵中的O（N），而列表中的O（1）以及列表中的O（N个相邻节点）中的相邻节点，而不是O（N）为矩阵。
这些地方包括Cormen等人的书或StackOverFlow：使用邻接列表和邻接矩阵的图的大小？或维基百科。
然而，像使用压缩行存储表示一样使用稀疏矩阵表示，内存需求仅在O（非零数）= O（边数），这与使用列表相同。从一个节点出来的边的数量是O（1）（它直接存储在CRS中），并且相邻的节点可以在O（num相邻节点）中列出。
为什么不讨论它？我应该假设CSR 是是由矩阵表示的图的邻接列表表示形式吗？或者说，矩阵是内存密集型的缺陷，因为他们不考虑稀疏矩阵表示形式的论据？
谢谢！
例如，要获得两跳以上的邻近矩阵，您只需对矩阵进行平方处理。我已经用适度的CPU时间在维基百科链接结构的稀疏矩阵表示中成功完成了这项工作。
I'm preparing for a coding interview, and was refreshing my mind on graphs. I was wondering the following : in all places I've seen, it is assumed that adjacency lists are more memory efficient than adjacency matrices for large sparse graphs, and should thus be preferred in that case. In addition, computing the number of outgoing edges from a node requires O(N) in a matrix while it's O(1) in a list, as well as which are the adjacent nodes in O(num adjacent nodes) for the list instead of O(N) for the matrix.
Such places include Cormen et al.'s book, or StackOverFlow : Size of a graph using adjacency list versus adjacency matrix? or Wikipedia.
However, using a sparse matrix representation like with Compressed Row Storage representation, the memory requirement is just in O(number of non-zeros) = O(number of edges), which is the same as using lists. The number of outgoing edges from a node is O(1) (it is directly stored in CRS), and the adjacent nodes can be listed in O(num adjacent nodes).
Why isn't it discussed ? Should I assume that CSR is a kind of adjacency list representation of the graph represented by the matrix ? Or is the argument that matrices are memory intensive flawed because they don't consider sparse matrix representations ?
Thanks!
Not everyone uses sparse matrix representations every day (I just happen to do so :), so I guess nobody thought of them. They are a kind of intermediate between adjacency lists and adjacency matrices, with performance similar to the first if you pick the right representation, and are very convenient for some graph algorithms.
E.g., to get a proximity matrix over two hops, you just square the matrix. I've successfully done this with sparse matrix representations of the Wikipedia link structure in modest amounts of CPU time.
这篇关于图表示法：邻接表与矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
