隣接行列を使ってグラフを表現するC++プログラムの解説

グラフの隣接行列（Adjacency Matrix）とは、サイズが V × V の正方行列のことです。ここでの V はグラフ G の頂点数を表します。行列の行と列にはそれぞれ頂点が対応しており、頂点 i から頂点 j への辺が存在する場合は、i 行 j 列の要素に「1」（重み付きグラフの場合は非ゼロの値）を格納します。辺が存在しない場合は、その位置には「0」が入ります。

隣接行列表現の計算量

• 隣接行列は計算時に O(V²) の記憶領域を必要とします。グラフが最大数の辺を持つ場合でも最小数の辺しか持たない場合でも、必要なメモリ量は同じです。つまり、辺の数に依存せず常に V × V 分の領域を確保することになります。

この特性から、隣接行列は辺の数が多い密なグラフ（Dense Graph）に向いており、逆に辺の数が少ない疎なグラフ（Sparse Graph）では無駄なメモリが多くなるという欠点があります。

入力例

以下のような6つの頂点（0〜5）と9本の辺を持つ無向グラフを考えます。

出力結果（隣接行列）

対称性に注目してください。無向グラフの場合、頂点 u から v への辺は頂点 v から u への辺でもあるため、行列は主対角線に対して対称になります。

アルゴリズム：add_edge(u, v)

入力 − 辺 {u, v} を構成する2つの頂点 u と v

出力 − グラフ G の隣接行列

Begin
   adj_matrix[u, v] := 1
   adj_matrix[v, u] := 1
End

有向グラフの場合は adj_matrix[v, u] := 1 の行を削除し、一方向のみ設定すれば対応できます。

C++サンプルコード

#include<iostream>
using namespace std;
int vertArr[20][20]; // 隣接行列（初期値はすべて0）
void displayMatrix(int v) {
   int i, j;
   for(i = 0; i < v; i++) {
      for(j = 0; j < v; j++) {
         cout << vertArr[i][j] << " ";
      }
      cout << endl;
   }
}
void add_edge(int u, int v) { // 辺を行列に追加する関数
   vertArr[u][v] = 1;
   vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
   int v = 6; // グラフの頂点数は6
   add_edge(0, 4);
   add_edge(0, 3);
   add_edge(1, 2);
   add_edge(1, 4);
   add_edge(1, 5);
   add_edge(2, 3);
   add_edge(2, 5);
   add_edge(5, 3);
   add_edge(5, 4);
   displayMatrix(v);
}

実行結果

0 0 0 1 1 0
0 0 1 0 1 1
0 1 0 1 0 1
1 0 1 0 0 1
1 1 0 0 0 1
0 1 1 1 1 0

コードのポイント

• vertArr[20][20]: 最大20個の頂点に対応できる静的な2次元配列として隣接行列を宣言しています。グローバル変数のため、初期状態ではすべての要素が0になっています。

• add_edge(u, v): 辺を追加するたびに、両方向の要素に1を代入します。これにより無向グラフの対称性が保たれます。

• displayMatrix(v): 頂点数 v を受け取り、v × v の範囲で行列の中身を出力する補助関数です。

• 頂点間の接続確認は O(1) で行えるため、「u と v は隣接しているか？」という問い合わせが高速に行えるのが隣接行列の大きな利点です。