隣接リスト

2025年10月21日

隣接リスト

英語表記: Adjacency List

概要

隣接リストは、コンピュータサイエンスにおける「データ構造（リスト, スタック, キュー, ツリー）」の範疇、特に「グラフ構造」を表現するための、非常に効率的な手法の一つです。グラフの頂点（ノード）間の接続関係（辺、エッジ）を、リスト構造（配列や連結リスト）を組み合わせて表現します。この表現方法は、グラフが持つ接続情報のみを記録するため、辺の数が少ない「疎なグラフ」を扱う際に、メモリ使用量を大幅に節約できるという特長を持っています。

詳細解説

隣接リストは、私たちが現在学んでいる「データ構造（リスト, スタック, キュー, ツリー） → グラフ構造 → 表現方法」という流れの中で、グラフを表現するための二大手法（もう一つは隣接行列）の一つとして位置づけられています。その目的は、グラフの構造をメモリ上で忠実に、かつ効率的に再現することにあります。

構成要素と動作原理

隣接リストは、基本的に二重の構造から成り立っています。

頂点リスト（メイン配列）: グラフに含まれるすべての頂点を格納するための土台となるリスト（多くの場合、配列が用いられます）。これは、グラフのすべての要素にアクセスするためのインデックスの役割を果たします。
隣接頂点リスト（サブリスト）: 頂点リストの各要素（各頂点）に付随する形で、その頂点と直接つながっている他の頂点群を格納するリストです。このサブリストには、頂点のIDや、重み付きグラフであれば辺のコスト情報などが含まれます。

動作の流れはシンプルですが強力です。例えば、「頂点Aから直接行ける場所はどこか？」を知りたい場合、まず頂点リストの中からAを探し出し、Aに紐づけられている隣接頂点リストを参照するだけで、すべての接続先を瞬時に把握できます。

階層構造における重要性（データ構造とグラフ表現）

なぜこの表現方法が重要なのでしょうか。それは、グラフ構造が現実世界（ネットワーク、交通網など）をモデル化する際に必須であるにもかかわらず、その表現方法によって計算資源の消費が大きく変わるからです。

隣接リストがリスト構造を基礎としている点は、この階層構造（データ構造）の文脈で特に注目すべきです。リストは、要素の追加や削除が比較的容易で、必要な分だけメモリを動的に確保できる特性を持っています。

隣接リストが優位性を発揮するのは、グラフの辺の数が頂点の数に比べて非常に少ない「疎グラフ」の場合です。

隣接行列は、V個の頂点がある場合、V×Vの二次元配列（行列）を常に使用します。辺が存在しない場合でも、その関係を「0」として記録するため、無駄なメモリが発生します（$O(V^2)$）。
隣接リストは、頂点の数（V）と辺の数（E）に比例するメモリだけを使用します（$O(V+E)$）。辺が存在しない場所は記録しないため、非常にコンパクトです。

もし私たちが扱うグラフが非常に大規模で、かつ接続がまばらな場合（例：地球上の都市と、その間に存在する数少ない直行便のネットワーク）、隣接リストを採用することで、メモリ消費を劇的に抑えることが可能になるのです。これは、限られた計算資源を効率的に使う、データ構造設計の妙と言えるでしょう。

具体例・活用シーン

隣接リストは、私たちが日々利用している多くのシステムで、ネットワークや接続関係を管理するために裏側で活躍しています。

活用シーンの例

ソーシャルネットワークサービス（SNS）: ユーザー（頂点）とその友達関係やフォロー関係（辺）を管理する際に利用されます。特にSNSの友達関係は、全体から見れば非常に疎なグラフであるため、隣接リストはメモリ効率の面で最適です。
Webクローラー: Webページ（頂点）間のハイパーリンク（辺）をたどって情報を収集する際、どのページからどのページへリンクが貼られているかを効率的に管理するために使われます。
地図情報システム（GIS）: 道路の交差点（頂点）と、その間の道路（辺）の接続情報や距離を管理します。ナビゲーションシステムが最短経路を探索する際（ダイクストラ法など）、隣接リストは隣接する交差点を高速に列挙するために使われます。

初心者向けのアナロジー：秘密結社の名簿

隣接リストの仕組みを理解するために、ある秘密結社「データ構造団」の名簿管理の物語を想像してみましょう。

この組織には多くの構成員（頂点）がいますが、秘密保持のため、各構成員は限られた数人の仲間（辺）としか直接連絡を取りません。

団長は、構成員全員が誰とつながっているかを記録するように命じました。

隣接行列方式を採用した場合、団員全員の名前を縦軸と横軸に書き出し、巨大な「連絡可能チェック表」を作ります。連絡可能なら「○」、不可能なら「×」を書き込みます。この表は、構成員が100人いれば1万マス、1,000人いれば100万マス必要になります。ほとんどのマスは「×」で埋まり、紙（メモリ）の無駄が大変です。

隣接リスト方式を採用した場合、団長は別の賢い方法を考えました。

まず、全構成員（頂点）の名前をリストアップしたメインの名簿を作成します。
次に、各構成員には、自分が直接連絡を取る相手の名前だけを書き込んだ「秘密の連絡先メモ」を持たせます。

もし団長が「構成員Aが誰と連絡を取れるか」を知りたければ、メインの名簿でAを探し、Aが持っている秘密の連絡先メモ（隣接リスト）を見るだけで済みます。Aの友達が少なければ、そのメモは短い紙切れで済みます。

この隣接リスト方式なら、組織全体の連絡網がどれだけ大規模になっても、記録するのは「実際に存在する連絡（辺）」の情報だけです。これにより、紙（メモリ）を最小限に抑えつつ、必要な情報を素早く引き出すことができるのです。

資格試験向けチェックポイント

日本のIT資格試験（ITパスポート、基本情報技術者、応用情報技術者）では、グラフの表現方法に関する知識は必須であり、特に隣接行列との比較として隣接リストが頻繁に出題されます。「データ構造 → グラフ構造 → 表現方法」という位置づけをしっかり理解しておきましょう。

メモリ効率: 隣接リストは、グラフの頂点数 $V$ と辺の数 $E$ を用いて $O(V+E)$ の記憶領域を必要とします。隣接行列の $O(V^2)$ と比較して、疎グラフ（辺が少ないグラフ）において圧倒的に有利である点を必ず覚えてください。
処理速度のトレードオフ:
- 隣接頂点の列挙: 特定の頂点から直接つながっているすべての頂点を調べるのは、隣接リストの方が高速です（リストをたどるだけ）。
- 辺の存在確認: 「頂点Aと頂点Bの間に辺が存在するか？」を調べる場合、隣接リストではAの隣接リスト全体を検索する必要があるため、隣接行列（行列の(A, B)要素を1回参照するだけ）より時間がかかる可能性があります。
適用の判断: グラフの密度（辺の多さ）によって、隣接リストと隣接行列のどちらを選ぶべきか判断させる問題が出ます。疎グラフには隣接リスト、密グラフ（辺が多いグラフ）には隣接行列が適している、という原則を理解しておきましょう。
実装方法: 隣接リストの実装には、配列の配列（JavaのArrayListなど）や、ハッシュテーブルと連結リストの組み合わせなど、様々なデータ構造の知識が複合的に使われることを理解しておくと、応用情報技術者試験などで役立ちます。