グラフとその表現方法を徹底解説|隣接行列・辺リスト・隣接リストの違い

グラフ(Graph)は、非線形データ構造の一つです。データをノード(頂点)で表現し、ノード間の関係をエッジ(辺)で表します。グラフGは「頂点(Vertices)」と「辺(Edges)」という2つの要素から構成され、頂点は集合V、辺は集合Eで表されるため、グラフは一般的にG(V, E)という記法で表されます。まずは具体例を見てみましょう。

上のグラフには、5つの頂点と5つの辺が存在します。すべての辺には向きが定められています。例として、頂点BとDを結ぶ辺に注目すると、始点はB、終点はDとなります。つまり、BからDへは移動できますが、DからBへは移動できません。このように向きを持つ辺を持つグラフを「有向グラフ」と呼びます。

グラフは非線形であり、配列のような規則的な構造を持たないため、メモリ上でグラフを表現するにはいくつかの方法が考案されています。主な表現方法は以下の3つです。

• 隣接行列(Adjacency Matrix)による表現
• 辺リスト(Edge List)による表現
• 隣接リスト(Adjacency List)による表現

隣接行列(Adjacency Matrix)による表現

グラフは隣接行列を使って表現できます。隣接行列とは、要素が0か1の二値を取る正方行列のことです。i行j列の要素は、頂点iから頂点jへの辺が存在する場合に「1」、存在しない場合に「0」となります。なお、無向グラフを隣接行列で表現する場合、iからjへの辺とjからiへの辺は常に同時に存在するため、行列は必ず対称行列になります。

辺リスト(Edge List)による表現

グラフは1次元配列を使って表現することもできます。この表現方法は「辺リスト」と呼ばれます。上の例では5つの辺が存在し、各辺について配列の最初の要素が始点、2番目の要素が終点を表します。無向グラフを表現する場合は、辺が双方向に移動可能であるため、辺リストの要素数は2倍になります。

隣接リスト(Adjacency List)による表現

もう一つの代表的なグラフ表現方法が「隣接リスト」です。この表現は連結リスト(Linked List)を基盤としています。この手法では、各ノードが、その頂点と直接接続しているノードの一覧をリストとして保持します。そしてリストの末尾では、各ノードがnull値に接続されており、それがそのリストの終端であることを示しています。

このように、グラフの表現方法はそれぞれ特徴が異なります。隣接行列は辺の有無の判定が高速である一方、メモリ消費が大きく、隣接リストはメモリ効率に優れる一方、特定の辺の存在確認には時間がかかるといったトレードオフがあります。用途やグラフの性質(頂点数・辺数の比率など)に応じて、適切な表現方法を選択することが重要です。