グラフ構造の隣接リスト（Adjacency List）とは？基本概念と実装方法を解説

グラフは代表的な非線形データ構造の一つです。頂点（ノード）でデータを表し、その頂点同士の関係を辺（エッジ）で表現します。グラフGは「頂点の集合V」と「辺の集合E」という2つの要素から構成され、G(V,E)という形式で表記されます。まずは具体例を見てみましょう。

このグラフには5つの頂点と5つの辺が存在します。すべての辺には向きが定義されています。例として、頂点BとDを結ぶ辺に注目すると、始点はB、終点はDとなります。そのため、BからDへは移動できますが、逆にDからBへ移動することはできません。

グラフは非線形であり、一定の規則性を持たない構造です。そのため、メモリ上でグラフを扱うには、目的に応じたいくつかの表現方法を使い分ける必要があります。主な表現方法は以下の3つです。

• 隣接行列による表現
• 辺リストによる表現
• 隣接リストによる表現

本記事では、この中から「隣接リスト」による表現方法について詳しく見ていきます。

隣接リストによるグラフの表現

隣接リストは、連結リストをベースとしたグラフの表現方法です。この手法では、各頂点が「その頂点と直接つながっている他の頂点の一覧」をリストとして保持します。そして各リストの末尾にはnull値が接続されており、そこがリストの終端であることを示しています。

隣接リストは、頂点数に対して辺の数が少ない疎なグラフを効率的に表現できる点が大きな特徴です。必要なメモリ領域をO(V+E)に抑えられるほか、特定の頂点に隣接する頂点を順番に辿る処理も高速に行えます。一方で、2つの頂点が直接つながっているかどうかを確認する場合には、リストを走査する必要があるため、隣接行列よりも時間がかかることがあります。このように、隣接リストと隣接行列にはそれぞれ利点・欠点があるため、扱うグラフの性質や実行したい処理に応じて適切な表現方法を選択することが重要です。