圖表示法：鄰接列表與矩陣

Question

我正準備進行編碼訪問，並在圖形上刷新了我的想法。我想知道以下幾點：在我見過的所有地方，都假定鄰接表比鄰接矩陣更適合大型稀疏圖，因此在這種情況下應該是首選。另外，計算一個節點的輸出邊的數量需要一個矩陣中的O（N），而列表中的O（1）以及列表中的O（N個相鄰節點）中的相鄰節點，而不是O（N）爲矩陣。
這些地方包括Cormen等人的書或StackOverFlow：Size of a graph using adjacency list versus adjacency matrix?或維基百科。然而，像使用壓縮行存儲表示一樣使用稀疏矩陣表示，內存需求恰好在O（非零數）= O（邊數）上，這與使用列表相同。一個節點的輸出邊的數量爲O（1）（它直接存儲在CRS中），並且相鄰節點可以列在O（num個相鄰節點）中。
爲什麼不討論？我是否應該假定CSR 是一種由矩陣表示的圖的鄰接表表示？或者說，矩陣由於不考慮稀疏矩陣表示而導致內存密集性存在缺陷？

謝謝！

Answer 1

不是每個人每天都會使用稀疏矩陣表示法（我只是碰巧這樣做:)，所以我猜想沒有人想到它們。它們是鄰接列表和鄰接矩陣之間的一種中介，如果選擇正確的表示，性能與第一種類似，並且對於某些圖算法非常方便。

例如，爲了得到兩跳的鄰近矩陣，你只需要square the matrix。我已經在CPU數量適中的情況下用Wikipedia link structure的稀疏矩陣表示成功地完成了這項工作。