隣接リスト
From Wikipedia, the free encyclopedia
| 上図のグラフは以下のような隣接リスト表現を持つ: | |||
| 1 | は | 2,3 | と隣接 |
| 2 | は | 1,3 | と隣接 |
| 3 | は | 1,2,4 | と隣接 |
| 4 | は | 3 | と隣接 |
計算機科学において、隣接リストはグラフを表すデータ構造と密接な関係がある。隣接リスト表現では、各頂点について、1つの辺でその頂点とつながっている全ての他の頂点のリストを作る（これがその頂点の「隣接リスト」である）。例えば、ヴァンロッサムが示唆した表現では、各頂点とその隣接する頂点群の配列をハッシュテーブルで関連付ける[1]。これは隣接リスト表現のインスタンスの1つと考えられる。また、Cormen らの表現では、頂点の番号をインデックスとする配列に各頂点の隣接する頂点群の片方向リストへの参照を格納する[2]。
隣接リスト構造の問題点は、グラフの辺についてのデータ（例えば、長さ、コストなど）を格納する明確な場所がない点である。その解決策として、例えば Goodrich と Tamassia の著書では、よりオブジェクト指向的に隣接リスト構造を変形し、各頂点に接合する辺を表したオブジェクトのリストを格納するオブジェクト（incidence list と呼ぶ）を提案している[3]。この構造を完成させるには、各辺から2つの端点の頂点への参照を行う必要がある。このバージョンの隣接リストでは、辺オブジェクトが追加されるため、頂点だけをリストにしているものよりもメモリを余分に消費する。しかし、辺に関する情報を格納するには便利である。
