C++でグラフの隣接行列を実装する方法【サンプルコード付き解説】

隣接行列とは

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

なお、無向グラフの場合、辺は双方向につながりを持つため、隣接行列は必ず対称行列になります。つまり、adj[i][j]とadj[j][i]は常に同じ値となります。

隣接行列表現の計算量

• 空間計算量： 隣接行列にはO(V²)のメモリが必要です。グラフが持つ辺の数が多くても少なくても、必要なメモリ容量は同じです。そのため、辺の数が頂点数に比べて非常に少ない「スパースなグラフ」では、メモリを無駄に消費する可能性があります。
• 辺の追加・削除： O(1)の時間で実行できます。
• 辺の存在確認： 2つの頂点間に辺が存在するかどうかをO(1)で即座に判定できます。

入力と出力の例

入力： 6つの頂点と9つの辺からなる無向グラフ

出力： 以下のような隣接行列が得られます。

アルゴリズム

add_edge(u, v)

入力： 辺{u, v}を構成する頂点uとv

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

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

無向グラフの場合、辺は双方向に存在するため、(u, v)と(v, u)の両方の要素に1を設定します。

C++による実装例

以下は、隣接行列を使ってグラフを表現し、辺を追加して結果を表示するC++プログラムの完全なコードです。

#include<iostream>
using namespace std;
int vertArr[20][20]; //隣接行列（初期値はすべて0）
int count = 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;
}

int 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

まとめ

隣接行列は、グラフを表現するためのシンプルで直感的なデータ構造です。辺の追加や存在確認がO(1)で行えるという大きな利点がある一方で、頂点数の2乗に比例したメモリを消費するため、頂点数が多く辺が少ないグラフには隣接リストの方が適しています。グラフの性質や用途に応じて、最適な表現方法を選択することが重要です。