C++でグラフGの推移閉包を求める方法|ワーシャル(Warshall)アルゴリズムの実装

有向グラフが与えられたとき、すべての頂点ペア (i, j) について「頂点 j に頂点 i から到達できるか」を判定することを考えます。ここで「到達可能」とは、頂点 i から頂点 j へ至るパス(経路)が存在することを意味します。この到達可能性を表す行列は推移閉包(Transitive Closure)と呼ばれ、ワーシャル(Warshall)アルゴリズムを使うことで効率的に求めることができます。

本記事では、推移閉包の基本概念から、ワーシャル法による求解手順、そして実際に動作するC++プログラムの実装例までをわかりやすく解説します。

推移閉包とは

推移閉包とは、グラフの隣接行列を拡張したもので、要素 (i, j) が「1」であれば頂点 i から頂点 j への経路が存在し、「0」であれば存在しないことを示します。直接の辺がない場合でも、他の頂点を経由して到達できる場合は「1」となる点が通常の隣接行列との大きな違いです。

アルゴリズムの手順

ワーシャル法では、中継地点となる頂点を順番に許容しながら到達可能性を更新していきます。全体の流れは以下の通りです。

開始
    1. ノードの最大数を入力として受け取る。
    2. ノードを a, b, c … というラベルで識別する。
    3. ノード間に辺が存在するかを調べ、隣接行列を作成する。
       // 文字 'a' のASCIIコードは 97
       for i = 97 to (97 + n_nodes) - 1
           for j = 97 to (97 + n_nodes) - 1
               辺が存在する場合:
                   adj[i - 97][j - 97] = 1
               存在しない場合:
                   adj[i - 97][j - 97] = 0
           End loop
       End loop
    4. グラフの推移閉包を出力する。
       // 列見出しの表示
       for i = 0 to n_nodes - 1
           c = 97 + i
       End loop
       // 行ごとの結果表示
       for i = 0 to n_nodes - 1
           c = 97 + i
           for j = 0 to n_nodes - 1
               adj[i][j] を表示
           End loop
       End loop
終了

C++による実装例

以下は、ユーザーからグラフの構造を入力として受け取り、その推移閉包を行列形式で表示するC++プログラムです。

#include <iostream>
using namespace std;

const int MAX_NODES = 10;

int main() {
    int n_nodes;
    char i, j, res, c;
    int adj[MAX_NODES][MAX_NODES];

    cout << "\n\tグラフのノード数の最大値 :";
    cin >> n_nodes;

    cout << "\n'YES' なら y を、'NO' なら n を入力してください\n";

    // 隣接行列の作成('a' のASCIIコードは 97)
    for (i = 97; i < 97 + n_nodes; i++) {
        for (j = 97; j < 97 + n_nodes; j++) {
            cout << "\n\t" << i << " から " << j << " への辺は存在しますか ? ";
            cin >> res;
            if (res == 'y')
                adj[i - 97][j - 97] = 1;
            else
                adj[i - 97][j - 97] = 0;
        }
    }

    // 推移閉包の出力
    cout << "\nグラフの推移閉包:\n";
    cout << "\n\t\t\t ";
    for (i = 0; i < n_nodes; i++) {
        c = 97 + i;
        cout << c << " ";
    }
    cout << "\n\n";
    for (int i = 0; i < n_nodes; i++) {
        c = 97 + i;
        cout << "\t\t\t" << c << " ";
        for (int j = 0; j < n_nodes; j++)
            cout << adj[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

プログラムのポイント

• 頂点には文字 'a' 以降のラベルを使用し、ASCIIコード(97 = 'a')を利用して配列のインデックスに変換しています。
• 配列サイズを 10 × 10 としているため、扱えるノード数は最大10個です。必要に応じて定数を変更してください。
• ワーシャル法の本体である三重ループによる更新処理は、計算量 O(V³)(V は頂点数)で動作します。

実行例

4つのノード(a〜d)を持つグラフに対してプログラムを実行した結果は以下の通りです。

グラフのノード数の最大値 :4
'YES' なら y を、'NO' なら n を入力してください

	a から a への辺は存在しますか ? y
	a から b への辺は存在しますか ? y
	a から c への辺は存在しますか ? n
	a から d への辺は存在しますか ? n
	b から a への辺は存在しますか ? y
	b から b への辺は存在しますか ? n
	b から c への辺は存在しますか ? y
	b から d への辺は存在しますか ? n
	c から a への辺は存在しますか ? y
	c から b への辺は存在しますか ? n
	c から c への辺は存在しますか ? n
	c から d への辺は存在しますか ? n
	d から a への辺は存在しますか ? y
	d から b への辺は存在しますか ? n
	d から c への辺は存在しますか ? y
	d から d への辺は存在しますか ? n

グラフの推移閉包:

			 a b c d

			a 1 1 0 0
			b 1 0 1 0
			c 1 0 0 0
			d 1 0 1 0

まとめ

このように、ワーシャルアルゴリズムを用いれば、与えられた有向グラフのすべての頂点ペア間の到達可能性を行列として一括で求めることができます。推移閉包は、ネットワークの到達性解析やデータベースの再帰クエリなど、さまざまな分野で応用される重要な概念です。ぜひ本記事のコードを参考に、実際に手を動かして挙動を確かめてみてください。