隣接リスト

隣接リストの概要

隣接リストとは、グラフ理論において、グラフを構成する頂点や辺をリスト形式で表現する手法です。この構造では、各頂点に接続している他の頂点の情報がリストとして格納されます。一般的に、このリストの順序には特別な規則はなく、頂点間の関係性を直感的に把握することが可能です。

計算機科学における隣接リストの応用

計算機科学の分野では、隣接リストがグラフを表現するための重要なデータ構造とされています。各頂点に対して、その頂点と直接接続されているすべての他の頂点のリストを作成します。たとえば、ヴァンロッサムが提案した方法では、各頂点とその隣接する頂点をハッシュテーブルを使って関連付けることで、隣接リストを実現しています。また、Cormenたちによって提案された別の手法では、頂点の番号をインデックスとして使用し、各頂点に隣接する頂点群への参照を配列に格納する形で表現されています。

隣接リストの課題

しかし、隣接リストは全ての情報を正確に管理できるわけではありません。特に、グラフの辺に関連する情報、例えば長さやコストを管理するための場所が不足しています。この課題に対して、GoodrichとTamassiaはオブジェクト指向の観点から隣接リストを改良し、各頂点に接続する辺を示すオブジェクトを格納した「接合リスト」（incidence list）を提案しています。この形式では、各辺の両端の頂点への参照を含める必要があります。これにより、頂点のみのリストよりもメモリを多く消費しますが、辺に関する情報も蓄積する利点があります。

隣接リストと隣接行列のトレードオフ

隣接リストの代わりに使用されることが多いのが隣接行列です。特に、隣接行列はコンパクトな形式でグラフを表現できますが、グラフの疎な部分に関してはメモリを無駄に消費することがあります。隣接リストの場合、存在しない辺の情報を格納する必要がないため、無駄なメモリを抑えることが可能です。例えば、32ビット環境での単純な配列を使用して隣接リストを実装した場合、無向グラフでは約8eバイトのメモリが必要となります。この時、eは辺の数です。一方で、隣接行列では、頂点の情報を1ビットで表現できるため、n^2/8バイトと非常にコンパクトです。

隣接リストが隣接行列よりもメモリを消費するのは、グラフの密度が一定の値を超えたときであるため、グラフが十分に疎である必要があります。さらに、隣接リストは特定の操作に対する効率性も持っています。特定の頂点に隣接する頂点を探す場合、隣接リストでは簡単にその頂点のリストを参照できますが、隣接行列では行をスキャンする必要があり、O(n)の時間を要します。

参考文献

以下の文献は、隣接リストやグラフアルゴリズムについてのさらなる情報を提供しています。

• - Joe Celko (2004). Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann.
• - David Eppstein (1996年). ICS 161 Lecture Notes: Graph Algorithms.

このように、隣接リストはグラフの表現として非常に効果的な手法であり、特定の条件においては隣接行列よりも有用です。

もう一度検索