隣接リストとは？仕組み・メリット・グラフ構造での使い方をわかりやすく解説【グラフ表現の基本】

グラフ構造（Graph）を扱うとき、データをどのように格納するかは性能に大きく影響します。
その中でも最もよく使われるのが 隣接リスト（Adjacency List） です。

隣接リストは、グラフを“ノードごとに接続先を一覧化した構造”で表現する方法で、SNSの友達関係、地図の道、ネットワーク構造など、多くの分野で活用されています。

この記事では、隣接リストとは何か、どのように作るのか、メリット・デメリットまで初心者にわかりやすく解説します。

---

◆ 隣接リストとは？

隣接リストとは、
グラフの各ノードに対して、そのノードと隣接（つながっている）ノードの一覧を記録したデータ構造
のことです。

例：
A が B と C に接続し、B が A と D に接続するグラフの場合：

A: B, C
B: A, D
C: A
D: B

このように、ノードごとに接続先を列挙します。

---

◆ 隣接リストの構造イメージ

グラフ構造（ノードとエッジ）がこちら：

A — B — D
|
C

これを隣接リストで表すと：

A: B, C
B: A, D
C: A
D: B

非常に直感的で理解しやすい形式です。

---

◆ 隣接リストはどんなとき使う？

• ノード数が多い
• エッジが比較的少ない（疎グラフ）
• 全体よりも部分的なつながりを見たい
• 探索（DFS・BFS）を効率化したい

特に SNS構造やWebリンクのような大規模グラフには最適です。

---

◆ 隣接リストのメリット

● 1. メモリ効率が良い

エッジ数だけを格納すればよいため、
疎グラフに非常に強い。

例：ノード100万でも、つながりが少なければ小さなデータで済む。

---

● 2. 隣接ノードの取得が高速

あるノードに接続するノードを全て簡単に取り出せる。

---

● 3. BFS・DFSとの相性が抜群

幅優先探索／深さ優先探索で最も使いやすい構造です。

---

● 4. 実装が簡単

言語の辞書（連想配列）やリストで簡単に実装できます。

例：Python

graph = {
  "A": ["B", "C"],
  "B": ["A", "D"],
  "C": ["A"],
  "D": ["B"]
}

---

◆ 隣接リストのデメリット

● 1. 任意の2ノード間の接続チェックは遅い

隣接ノードのリストから探索するため、
最悪で O(n) が必要。

---

● 2. 完全グラフ（すべてがつながる）には不向き

全ノードがすべて接続するような場合、
隣接行列の方が高速になることもある。

---

● 3. 固定配列のようなランダムアクセスは弱い

連想配列＋リストの形になるため、
行列に比べてアクセス形式が複雑。

---

◆ 隣接リストと隣接行列の比較

項目	隣接リスト	隣接行列
メモリ効率	良い（疎グラフ向け）	悪い（密グラフ向け）
隣接ノードの取得	速い	やや遅い
ノード間の接続確認	遅い	O(1)で高速
実装難易度	低い	中

用途によって使い分けが必要です。

---

◆ 隣接リストはどこで使われている？

• SNS（フォロー・友達関係の構造）
• ネットワークルーティング
• 検索エンジンのリンク解析
• 推薦システム（似ている商品のリスト化）
• データベースのグラフ構造
• 経路探索アルゴリズム（BFS/DFS）
• AIの知識グラフ

大規模で複雑な関係性データの管理に最適です。

---

◆ まとめ：隣接リストは「グラフを軽量に表現する」ための基本形式

隣接リスト（Adjacency List）は、

• ノードごとの接続関係をリストで管理する
• メモリ効率が高く、疎グラフに最適
• BFS・DFSなどの探索アルゴリズムで必須
• 大規模データのグラフ表現に強い
• SNS・地図・Webなど多くのシステムで利用される

という特徴を持ち、グラフ構造を扱う際の基本的かつ重要なデータ格納形式です。