隣接行列

隣接行列

隣接行列

英語表記: Adjacency Matrix

概要

隣接行列(りんせつぎょうれつ)は、「データ構造」の中でも特にグラフ構造をコンピュータ上で効率的に扱うための表現方法の一つです。これは、グラフに含まれるノード(頂点)間の接続関係(エッジ、辺)を、数学的な二次元の表、すなわち行列(マトリックス)形式で表現する手法です。グラフの接続状況が一目でわかるように数値化されるため、接続性の確認や経路探索などのアルゴリズム処理の基盤となります。

詳細解説

隣接行列は、私たちが現在学んでいる「データ構造(リスト, スタック, キュー, ツリー) → グラフ構造 → 表現方法」という文脈において、グラフをどのように表現するかという重要な選択肢を提供します。

目的と構造

グラフ構造は、ノードとエッジから構成される複雑な関係性を示すため、コンピュータのメモリ上にそのまま格納することはできません。そこで、隣接行列はノードの数を $N$ とした場合、$N \times N$ のサイズの正方行列(二次元配列)を用いて、この複雑な関係性をシンプルに表現します。

この行列の各要素 $A[i][j]$ は、ノード $i$ からノード $j$ へエッジが存在するかどうかを示します。

  1. エッジが存在する場合: 要素 $A[i][j]$ には通常「1」が格納されます。
  2. エッジが存在しない場合: 要素 $A[i][j]$ には通常「0」が格納されます。

もしグラフが重み付きグラフ(エッジに距離やコストなどの重みが設定されている場合)であれば、「1」の代わりにその重み値自体を格納します。エッジがない場合は、計算上の便宜を図るために無限大を意味する特別な値($\infty$)や「0」が用いられることもあります。

動作原理と特徴

隣接行列の最大の利点は、接続性の確認が非常に高速である点にあります。

例えば、「ノードAとノードBが直接つながっているか?」を知りたい場合、行列の対応する位置 $A[A][B]$ を参照するだけで済みます。この操作は、計算量でいうと $O(1)$(定数時間)で完了するため、非常に効率的です。

しかし、この表現方法には欠点もあります。グラフのノード数が $N$ の場合、行列のサイズは $N^2$ となります。もしグラフが疎グラフ(エッジが少ないグラフ)であったとしても、すべての $N^2$ のマス目を用意しなければなりません。そのため、ノード数が非常に多い大規模な疎グラフを扱う場合、多くのメモリ空間を無駄にしてしまう可能性があります。これは、データ構造を設計する上で常に考慮すべきトレードオフの一つですね。

有向グラフと無向グラフ

隣接行列は、グラフの種類によって表現が少し異なります。

  • 無向グラフ: エッジ $i-j$ は $i$ から $j$ へも、$j$ から $i$ へも移動可能であることを意味します。この場合、行列は必ず対称行列になります($A[i][j] = A[j][i]$)。
  • 有向グラフ: エッジが一方通行(例:$i \to j$)の場合、$A[i][j]$ は 1 ですが、$A[j][i]$ は 0 になることがあります。

このように、隣接行列はグラフの性質(有向か無向か、重みがあるか)を明確に行列の構造に反映させることができる、非常に強力な表現方法なのです。

具体例・活用シーン

隣接行列の考え方は、身近なところにも応用されています。特に、関係性の有無を明確に示したい場合に有効です。

活用シーン:交通ネットワークの分析

隣接行列の代表的な活用例は、都市間の交通ネットワークです。

  • ノード: 主要な都市(東京、大阪、名古屋など)。
  • エッジ: それらの都市間を結ぶ直行の鉄道路線や高速道路。

このネットワークを隣接行列で表現すると、例えば「東京から大阪へ直行便があるか」は、行列の「東京」行と「大阪」列の交差するマスを見るだけで瞬時に判断できます。もし重み付きグラフであれば、そのマスには「移動にかかる時間」や「運賃」が格納されることになります。

アナロジー:社交ダンスのペアリング表

隣接行列を理解するための分かりやすい比喩として、「社交ダンスのペアリング表」を考えてみましょう。

あるダンスパーティーで、参加者(ノード)がいます。全員が誰とペアを組む可能性があるかを示す表を作成します。

  1. 参加者リスト: 縦軸(行)と横軸(列)に、参加者全員の名前(Aさん、Bさん、Cさん…)を並べます。
  2. 接続(ペアの可否):
    • もしAさんとBさんがペアを組むことができるなら、A行B列のマスに「1」を記入します。
    • もしAさんとCさんがペアを組むことができないなら、A行C列のマスに「0」を記入します。

このペアリング表こそが隣接行列です。この表があれば、「次に誰と誰が組めるか?」を瞬時に確認でき、スムーズにダンスの組み合わせを決めることができます。もし参加者が100人いた場合、100×100のマス目(10,000マス)が必要になりますが、一度作ってしまえば、誰と誰が繋がっているかを探すために、膨大なリストを端から端まで探す必要はありません。これが、隣接行列がもたらす高速な接続確認のメリットなのです。

資格試験向けチェックポイント

ITパスポート、基本情報技術者、応用情報技術者の試験では、データ構造としてのグラフの表現方法に関する知識は頻出です。特に隣接行列については、その特徴と、もう一つの主要な表現方法である「隣接リスト」との比較が重要になります。

| チェックポイント | 詳細と試験対策 |
| :— | :— |
| 隣接リストとの比較 | 最も重要です。隣接行列はメモリ使用量が $O(N^2)$(ノード数 $N$ の二乗)で固定されるのに対し、隣接リストは $O(N + E)$(ノード数 $N$ とエッジ数 $E$ の和)です。疎グラフの場合は隣接リストが有利、密グラフや接続確認の速度が必要な場合は隣接行列が有利、と覚えておきましょう。 |
| 空間計算量 | 隣接行列のメモリ使用量は $O(N^2)$ であることを理解してください。ノード数が2倍になれば、必要なメモリは4倍になるという関係性を問われることがあります。 |
| 接続確認の効率 | 任意の2ノード間の接続確認(エッジの有無)は $O(1)$(定数時間)で完了します。これは隣接行列の最大の強みであり、試験でメリットとして問われる点です。 |
| 無向グラフの特性 | 無向グラフの隣接行列は必ず対称行列になる(対角線を軸に左右対称)という性質は、簡単な計算問題や正誤問題として出題されやすいポイントです。 |
| 表現方法の文脈 | 「データ構造におけるグラフの表現方法」として、隣接行列が具体的にどのようなデータを格納し、どのような処理に適しているかを問われます。最短経路問題(ダイクストラ法など)の初期データとして使われることが多いという知識も役立ちます。 |

関連用語

  • 情報不足(隣接リスト、グラフ理論、空間計算量、最短経路問題などが関連しますが、このテンプレートでは情報不足とします。)
よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

この記事を書いた人

両親の影響を受け、幼少期からロボットやエンジニアリングに親しみ、国公立大学で電気系の修士号を取得。現在はITエンジニアとして、開発から設計まで幅広く活躍している。

目次