隣接リスト

各ノードが、そのノードに隣接するノードの番号のリストを持ちます。重みつきグラフの場合は、番号だけではなく重みもリストの要素に追加されます。リストの最後に番兵を設置しておくと便利です。

有向グラフ



重みつき有向グラフ

隣接リスト表現の特徴

• エッジの数に比例したメモリしか必要としない
• ノード u とノード v の関係を調べるには、リストを探索しなければならない
• エッジの追加・削除の操作が難しく、効率的に行えない
• 実装がやや難しい