隣接リスト

隣接リスト（りんせつリスト、英: adjacency list）は、グラフ理論でのグラフにある頂点または辺を全てリスト（一覧）で表現したものである。

一般に隣接リストでは順序は不定である。

計算機科学での応用

上図のグラフは以下のような隣接リスト表現を持つ:
1	は	2,3	と隣接
2	は	1,3	と隣接
3	は	1,2,4	と隣接
4	は	3	と隣接

計算機科学において、隣接リストはグラフを表すデータ構造と密接な関係がある。隣接リスト表現では、各頂点について、1つの辺でその頂点とつながっている全ての他の頂点のリストを作る（これがその頂点の「隣接リスト」である）。例えば、ヴァンロッサムが示唆した表現では、各頂点とその隣接する頂点群の配列をハッシュテーブルで関連付ける^[1]。これは隣接リスト表現のインスタンスの1つと考えられる。また、Cormen らの表現では、頂点の番号をインデックスとする配列に各頂点の隣接する頂点群の片方向リストへの参照を格納する^[2]。

隣接リスト構造の問題点は、グラフの辺についてのデータ（例えば、長さ、コストなど）を格納する明確な場所がない点である。その解決策として、例えば Goodrich と Tamassia の著書では、よりオブジェクト指向的に隣接リスト構造を変形し、各頂点に接合する辺を表したオブジェクトのリストを格納するオブジェクト（incidence list と呼ぶ）を提案している^[3]。この構造を完成させるには、各辺から2つの端点の頂点への参照を行う必要がある。このバージョンの隣接リストでは、辺オブジェクトが追加されるため、頂点だけをリストにしているものよりもメモリを余分に消費する。しかし、辺に関する情報を格納するには便利である。

トレードオフ

隣接リストの代替としては隣接行列がある。疎らな隣接行列となるグラフの場合、隣接リストの方がメモリを無駄にしない。これは、隣接リストの方が存在しない辺を表すメモリ領域を全く必要としないためである。32ビットのコンピュータ上で単純な配列による隣接リスト実装をすると、無向グラフでは8eバイトのメモリを必要とする。ここで、eは辺の数で、隣接リストでは辺が1つあると2箇所にそれに対応したデータが必要で、1つを4バイトと計算している。

一方、隣接行列では1カ所には1ビットで済むため、非常にコンパクトに表現でき、n²/8バイトしか要しない。ここで、nは頂点の数である。無駄な領域があるとしても、このコンパクトさは参照の局所性という点で好ましい。

n個の頂点のグラフでは、辺は最大でも（ループを許容しても）n²であり、ここで d = e/n² をグラフの密度とする。すると 8e > n²/8、すなわち隣接リストが隣接行列よりもメモリを消費するのは d > 1/64 のときである。したがって隣接リスト表現がメモリ使用量という面で正当化されるには、グラフが十分に疎らでなければならない。しかし、以上の分析はグラフの連結構造だけを表現する場合の話で、その他の数値情報を格納する場合はまた別の考察が必要である。

メモリ使用量のトレードオフとは別に、データ構造にはそれぞれ適した操作が存在する。ある頂点に隣接する頂点群を探すことは隣接リスト表現では容易であり、単にその頂点の隣接リストを見ればよい。隣接行列では、1つの行全体をスキャンする必要があり、O(n) の時間がかかる。2つの頂点を結ぶ辺があるかどうかを知りたい場合、隣接行列では1回の操作で済むが、隣接リストでは、リストをたどって調べる必要がある。

脚注・出典

^ Guido van Rossum (1998年). “Python Patterns — Implementing Graphs”. 2009年6月25日閲覧。
^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. pp. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7
^ Michael T. Goodrich and Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1

参考文献

Joe Celko (2004). Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann. excerpt from Chapter 2: "Adjacency List Model". ISBN 1-55860-920-2
David Eppstein (1996年). “ICS 161 Lecture Notes: Graph Algorithms”. 2009年6月25日閲覧。
AdjacencyList in Java

[1] Guido van Rossum (1998年). “Python Patterns — Implementing Graphs”. 2009年6月25日閲覧。

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. pp. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7

[3] Michael T. Goodrich and Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1

[1]

[2]

[3]