グラフを表すデータ構造(隣接行列と隣接リスト)

~目次~
・グラフを表すデータ構造
・隣接行列と隣接リストの比較
・余談

グラフを表すデータ構造

下図のようなネットワークっぽいものをグラフと言います(正確には頂点集合と辺集合のペアをグラフと言います)。

これを表現するデータ構造として隣接行列隣接リストというものがあります。

図のようなグラフを隣接行列、隣接リストそれぞれで表現してみます:

グラフ

隣接行列
$\begin{pmatrix}0&1&0&0\\0&1&1&0\\1&0&0&0\\0&0&0&0\end{pmatrix}$

辺があるところに $1$、ないところに $0$ を格納した行列です。例えば、頂点 $1$ から頂点 $2$ へ辺があるので、$12$ 成分($1$ 行目の $2$ 列目)が $1$ となっています。
隣接行列は、プログラム上では二次元配列で実現できます。

隣接リスト
$1\to$「$2$」というリスト
$2\to$「$2,3$」というリスト
$3\to$「$1$」というリスト
$4\to$ 空のリスト

各頂点について、自分から出ている辺の行き先をリスト化して表現したものです。例えば、頂点 $2$ からは頂点 $2$ と $3$ に行けるので「$2,3$」というリストを持っています。

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

隣接行列による表現は
×メモリが $|V|\times |V|$ くらい必要
○定数時間で特定の辺があるかどうか判定できる
×次数(特定の頂点から出ている辺の数)を求めるのが少し遅い
○隣接行列のかけ算や、固有値が意味を持つこともある

隣接リストによる表現は
○メモリが $|E|$ くらいあればよい(辺が少ないグラフでは有利)
×特定の辺があるかどうかの判定に、最悪 $O(|V|)$ の時間がかかる
○次数を求めるのが少し速い

それぞれに長所と短所があるので、やりたいことに応じてデータ構造を使い分けましょう。

余談

・無向グラフも同様に、隣接行列でも隣接リストでも表現できます。

・多重辺も扱えます。
隣接行列では、例えば各成分を辺の数とすれば表現できます。
隣接リストでは、同じ番号の重複を許せば表現できます。

・重み付きグラフも表現できます。
隣接行列では、例えば各成分を重みとすれば表現できます(多重辺かつ重み付きの場合は少し困りますが)。
隣接リストでは「行き先と重みのペアのリスト」を持てば表現できます。

次:編集距離(レーベンシュタイン距離)の求め方
前:スタックとキューの意味と例、覚え方

スポンサーリンク

スポンサーリンク

誤植がございましたら @mathwordsnet までご連絡をお願いいたします。
ページ上部へ戻る