コーディングの面接の準備をしていて、グラフについて頭をリフレッシュしていました。私は次のことを疑問に思っていました:私が見たすべての場所で、隣接リストは大規模なスパースグラフの隣接マトリックスよりもメモリ効率が高いと想定されているため、その場合は優先する必要があります。さらに、ノードからの発信エッジの数を計算するには、リストでは O(1) であるのに対し、マトリックスでは O(N) が必要です。行列の O(N)。
そのような場所には、Cormen らの本、または StackOverFlow : Size of a graph using adjacency list vs adjacency matrix?が含まれます。またはウィキペディア。
ただし、圧縮された行ストレージ表現のような疎行列表現を使用すると、メモリ要件は O(非ゼロの数) = O(エッジの数) になります。これは、リストを使用する場合と同じです。ノードからの発信エッジの数は O(1) (CRS に直接格納されます) であり、隣接ノードは O(隣接ノード数) にリストできます。
なぜ議論されないのですか？CSRは、マトリックスで表されるグラフの一種の隣接リスト表現であると想定する必要がありますか? それとも、疎行列表現を考慮していないため、行列がメモリ集約型であるという議論には欠陥がありますか?
ありがとう！