data-structures - リストと比較して、隣接行列でより優れたパフォーマンスを発揮するアルゴリズムはどれですか？

Question

隣接行列が隣接リストよりも優れているアルゴリズムはありますか？逆はどうですか？

Answer 1

実行時間に関しては、隣接行列はほとんどの場合リストよりも優れています。Listの実装では、グラフを格納するために使用するメモリ（エッジの数に比例）が少なくなります。

したがって、メモリが重要な場合（ノード数が多いスパースグラフの場合は確かにそうです）、リストを使用します。実行時間が重要で、グラフが密集している可能性がある場合は、隣接行列を使用します。