C++で2次元配列（隣接行列）を使ってグラフを表現する方法

本記事では、2次元配列（隣接行列）を使用してグラフを表現するC++プログラムを紹介します。隣接行列を用いることで、グラフの頂点同士の接続関係をシンプルかつ直感的に管理できるようになります。

このアルゴリズムの時間計算量はO(v×v)です（vは頂点数）。メモリ使用量が頂点数の2乗で増加するため、辺の数が比較的多い「密なグラフ」の表現に適した手法と言えます。

隣接行列とは

隣接行列とは、グラフの構造を v×v の正方行列で表現するデータ構造です。頂点 i と頂点 j が直接つながっている場合には行列の (i, j) 成分を 1 とし、つながっていない場合は 0 を格納します。無向グラフの場合、行列は必ず対称になります。

アルゴリズム

Begin
   頂点数「v」と辺数「e」を入力として受け取る。
   graph[][] 行列にメモリを割り当てる。
   グラフの「e」組の頂点ペアを graph[][] に入力する。
   接続された各頂点ペア (v1, v2) について、(v1, v2) と (v2, v1) の位置に 1 を格納する。
   PrintMatrix() を使って行列を出力する。
End

サンプルコード

#include<iostream>
#include<iomanip>
using namespace std;
void PrintMatrix(int **matrix, int n) {
    int i, j;
    cout<<"\n\n"<<setw(4)<<"";
    for(i = 0; i < n; i++)
        cout<<setw(3)<<"("<<i+1<<")";
    cout<<"\n\n";
    for(i = 0; i < n; i++) {
        cout<<setw(3)<<"("<<i+1<<")";
        for(j = 0; j < n; j++) {
            cout<<setw(4)<<matrix[i][j];
        }
        cout<<"\n\n";
    }
}
int main() {
    int i, v, e, j, v1, v2;
    cout<<"Enter the number of vertexes of the graph: ";
    cin>>v;
    int **graph;
    graph = new int*[v];
    for(i = 0; i < v; i++) {
        graph[i] = new int[v];
        for(j = 0; j < v; j++) graph[i][j] = 0;
    }
    cout<<"\nEnter the number of edges of the graph: ";
    cin>>e;
    for(i = 0; i < e; i++) {
        cout<<"\nEnter the vertex pair for edge "<<i+1;
        cout<<"\nV(1): ";
        cin>>v1;
        cout<<"V(2): ";
        cin>>v2;
        graph[v1-1][v2-1] = 1;
        graph[v2-1][v1-1] = 1;
    }
    PrintMatrix(graph, v);
}

コードのポイント

• 動的なメモリ確保：new 演算子により、実行時に入力される頂点数 v に応じた v×v の2次元配列を確保しています。
• ゼロ初期化：すべての要素を 0 で初期化し、「辺が存在しない状態」から出発します。
• 無向グラフへの対応：(v1, v2) と (v2, v1) の両方に 1 を設定することで、双方向の接続を表現しています。
• 整形された出力：iomanip ヘッダの setw() を活用し、行列の桁を揃えて見やすく表示します。
• 注意点：本コードでは簡潔さを優先してメモリ解放を省略していますが、実際の開発では使い終わった後に delete[] で解放することが推奨されます。

実行結果

Enter the number of vertexes of the graph: 5
Enter the number of edges of the graph: 4
Enter the vertex pair for edge 1
V(1): 2
V(2): 1
Enter the vertex pair for edge 2
V(1): 3
V(2): 2
Enter the vertex pair for edge 3
V(1): 1
V(2): 1
Enter the vertex pair for edge 4
V(1): 3
V(2): 1
(1) (2) (3) (4) (5)
(1) 1 1 1 0 0
(2) 1 0 1 0 0
(3) 1 1 0 0 0
(4) 0 0 0 0 0
(5) 0 0 0 0 0

この実行例では、頂点5個・辺4本の無向グラフを構築しています。入力された辺は「1–2」「2–3」「1–1（自己ループ）」「1–3」であり、行列の (1,1)、(1,2)、(1,3)、(2,1)、(2,3)、(3,1)、(3,2) の位置に 1 が格納されていることが確認できます。辺が存在しない頂点4と5の行・列はすべて 0 になっています。また、無向グラフであるため行列が対称になっている点にも注目してください。