グラフの推移閉包（Transitive Closure）とは？ワーシャル法によるアルゴリズムとC++実装を解説

グラフにおける推移閉包（Transitive Closure）とは、ある頂点 u から別の頂点 v へ「到達できるかどうか」を示す到達可能性行列のことです。1つのグラフが与えられたとき、すべての頂点ペア (u, v) について、u から v が到達可能かどうかを求めます。

最終的に得られる行列はブール型（0 と 1 のみ）で構成されます。頂点 u から頂点 v に対応する要素が 1 である場合、「u から v へ至る経路が少なくとも 1 本存在する」ことを意味します。逆に 0 であれば、いかなる経路を通っても u から v には到達できないことを表します。

この手法は、隣接行列に対して動的計画法を適用するものであり、ワーシャルのアルゴリズム（Warshall's Algorithm）として広く知られています。計算量は O(V³) であり、頂点数 V がそれほど大きくないグラフに対して効率的に機能します。

入力と出力

入力:
1 1 0 1
0 1 1 0
0 0 1 1
0 0 0 1

出力:
推移閉包行列
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1

アルゴリズム

transClosure(graph)

入力: 与えられたグラフ
出力: 推移閉包行列

Begin
    隣接行列を transMat という名前の別の行列にコピーする
    グラフ内の任意の頂点 k について、以下を繰り返す
        グラフ内の各頂点 i について、以下を繰り返す
            グラフ内の各頂点 j について、以下を繰り返す
                transMat[i, j] := transMat[i, j] OR (transMat[i, k] AND transMat[k, j])
            繰り返し終了
        繰り返し終了
    繰り返し終了
    transMat を表示する
End

この更新式は、「i から j へ直接到達できる」場合、または「i から k へ移動でき、さらに k から j へ移動できる」場合に transMat[i, j] を 1 にするというものです。中継地点となる頂点 k を順番にすべて試すことで、直接の辺がない頂点ペアへの間接的な経路もすべて反映されます。

C++による実装例

#include<iostream>
#include<vector>
#define NODE 4
using namespace std;

/* int graph[NODE][NODE] = {
    {0, 1, 1, 0},
    {0, 0, 1, 0},
    {1, 0, 0, 1},
    {0, 0, 0, 0}
}; */

int graph[NODE][NODE] = {
    {1, 1, 0, 1},
    {0, 1, 1, 0},
    {0, 0, 1, 1},
    {0, 0, 0, 1}
};

int result[NODE][NODE];

void transClosure() {
    for(int i = 0; i<NODE; i++)
        for(int j = 0; j<NODE; j++)
            result[i][j] = graph[i][j];   //最初にグラフを結果行列へコピーする
    for(int k = 0; k<NODE; k++)
        for(int i = 0; i<NODE; i++)
            for(int j = 0; j<NODE; j++)
                result[i][j] = result[i][j] || (result[i][k] && result[k][j]);
    for(int i = 0; i<NODE; i++) {         //結果行列を出力する
        for(int j = 0; j<NODE; j++)
            cout << result[i][j] << " ";
        cout << endl;
    }
}

int main() {
    transClosure();
}

出力

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

この実行結果を見ると、元のグラフでは直接の辺がつながっていなかった頂点ペアにも、他の頂点を経由して到達できる場合は 1 が設定されていることが確認できます。これにより、グラフ全体の到達可能性を一目で把握できるようになります。