グラフの表現：隣接リストと行列

Question

私はコーディングのインタビューの準備をしていて、グラフで私の心をリフレッシュしていました。私は次のことを疑問に思っていました。私が見たすべての場所で、隣接リストは大きなスパースグラフの隣接行列よりもメモリ効率が良いと想定されています。さらに、ノードから出て行くエッジの数を計算するには、行列中のO（N）が必要であり、O（1）はリスト内にあり、隣接するO（num隣接ノード）行列のO（N）
このような場所には、Cormen et al。の書籍、またはStackOverFlow：Size of a graph using adjacency list versus adjacency matrix?またはWikipediaがあります。

しかし、Compressed Row Storage表現のようなスパース行列表現を使用すると、メモリ要件はO（ゼロ以外の数）= O（エッジ数）になります。これはリストを使用する場合と同じです。ノードからの出力エッジの数はO（1）（これはCRSに直接格納されている）であり、隣接するノードはO（隣のノードの数）にリストすることができる。
なぜ議論されていないのですか？ CSR がであると仮定して、マトリックスによって表されるグラフの隣接関係リスト表現の一種ですか？あるいは、行列が疎行列表現を考慮していないために、メモリが集中していないという議論がありますか？

ありがとうございます！

Answer 1

誰もが毎日スパース行列表現を使用しているわけではありません（私はそうしています:)だから、誰もそれらを考えなかったと思います。それらは隣接リストと隣接行列の中間の一種で、正しい表現を選ぶと最初のものに似たパフォーマンスを持ち、いくつかのグラフアルゴリズムにとって非常に便利です。

たとえば、2つのホップでプロキシミティマトリックスを取得する場合は、ちょうどsquare the matrixです。私は、Wikipedia link structureの疎なマトリックス表記でCPU時間を適度にしてこれを成功させました。