読み方 ： りんせつぎょうれつ

概要

グラフ構造は、点を表す頂点と、それらを結ぶ線を表す辺から構成される構造であり、ネットワークや道路網、SNSの関係性など多様な対象を抽象化して扱うために用いられる。隣接行列はグラフの頂点間の接続の有無を表す行列で、頂点の数がnのとき、n行n列の正方行列として表現される。

行方向にも列方向にも頂点が同じ順番で並んでおり、行と列の交点にあたる要素に値を記録することで接続関係を示す。例えば、頂点iから頂点jへ辺が存在する場合、隣接行列A上の要素A_ijに1を書き入れ、存在しない場合に0を書き入れる。

無向グラフでは、頂点iと頂点jの接続に向きがない（i─j）ため、行列は主対角線を軸として対称となる。一方、有向グラフでは、iからjへの辺（i→j）とjからiへの辺（j→i）は区別されるため、行列は一般に非対称となる。また、辺に重みが付与される重み付きグラフでは、0や1の代わりに距離やコストなどの数値を要素に格納することがある。

隣接行列を作成することで、特定の二頂点間に辺が存在するかどうかを常に同じ短時間（定数時間）で判定できる。一方、頂点数が多く辺の数が少ない疎なグラフでは、実際には存在しない接続に対応する要素も含めてnの二乗に比例する記憶領域が必要となり無駄が多い。用途やグラフの性質に応じて隣接リストなど他の表現方法と使い分けられる。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。