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

接続行列（インシデンス行列）とは

グラフの接続行列（インシデンス行列）は、グラフをメモリ上に格納するためのもうひとつの表現方法です。隣接行列と異なり、接続行列は正方行列ではありません。そのサイズは V × E で表されます。ここで V はグラフの頂点数、E は辺の数です。

この行列では、各行に頂点が配置され、各列に辺が配置されます。ある辺 e {u, v} に対しては、列 e のうち頂点 u と頂点 v に対応する位置に「1」がマークされます。これにより、「どの頂点がどの辺に接続しているか」という情報を直感的に把握できます。

接続行列の計算量とメモリ使用量

• 接続行列による表現では、構築時に O(V × E) の記憶領域が必要になります。完全グラフの場合、辺の数は V(V−1)/2 となるため、接続行列は隣接行列に比べて大幅に多くのメモリを消費します。そのため、大規模なグラフを扱う場合には注意が必要です。

入力（グラフの例：6頂点・9辺）

出力（接続行列）

例えば、行0を見ると列E0とE1が1になっているため、頂点0は辺E0およびE1に接続していることが分かります。

アルゴリズム

add_edge(u, v)

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

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

処理の開始時点では、接続行列用の辺カウンタ ed_cnt は 0 に初期化されています。

Begin
   ed_cnt := ed_cnt + 1
   inc_matrix[u, ed_cnt] := 1
   inc_matrix[v, ed_cnt] := 1
End

つまり、新しい辺を追加するたびに辺番号を1つ進め、その列の頂点 u と v の行に 1 を設定します。

C++による実装例

#include<iostream>
using namespace std;
int inc_arr[20][20]; // 接続行列を保持する配列
int ed_no = 0;
void displayMatrix(int v, int e) {
    int i, j;
    for(i = 0; i < v; i++) {
        for(j = 0; j < e; j++) {
            cout << inc_arr[i][j] << " ";
        }
        cout << endl;
    }
}
void add_edge(int u, int v) { // 辺番号付きで行列に辺を追加する関数
    inc_arr[u][ed_no] = 1;
    inc_arr[v][ed_no] = 1;
    ed_no++; // 辺番号を増加させる
}
main(int argc, char* argv[]) {
    int v = 6; // グラフの頂点数は6
    int e = 9; // グラフの辺数は9
    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, e);
}

実行結果

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

このように、各行（頂点）ごとに「1」が立っている列（辺）を確認することで、グラフ全体の接続関係を読み取ることができます。無向グラフの場合は両端の頂点に 1 を設定しますが、有向グラフを扱う場合は始点に 1、終点に −1 を設定する拡張も一般的です。