隣接リスト

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

有向グラフ

_images/DUList.gif

重み付き有向グラフ

_images/DWList.gif

隣接リスト表現の特徴

エッジの数に比例したメモリしか必要としない.

ノード i と ノード j の関係を調べるには, リストを探索しなげればならない.

エッジの追加・削除の操作が難しく, 効率的に行えない.

実装がやや難しい.

Table Of Contents

Previous topic

隣接行列

Next topic

C 言語による初めてのアルゴリズム入門