推移閉包(transitive closure)、または、到達可能性全網羅

(有向)グラフにおいて、あるノードからあるノードへ到達可能であるときに、その２ノード間にエッジを加えて作成したグラフを、そのグラフの推移閉包と言う。一度この推移閉包を作成すれば、(有向)グラフにおける径路の有無の情報はすぐに得られる。密なグラフができるので、推移閉包は隣接行列で表現する方が適当なことが多い。推移閉包を計算するプログラムは極めて簡単であり、推移閉包の計算時間は疎グラフの場合に、密グラフの場合にである

今、あるグラフが隣接行列表現してあるとし、それがV個のノードからなるグラフがの行列N[i][j], 0<=i<=V-1,0<=j<=V-1,とする。隣接グラフにはエッジが存在するノード間は１、そうでない場合には０が記載されている。ノード数Vに関する３重ループにて次のようにして、推移閉包の隣接行列が得られる

//本ソースは未検証です

for(i=0;i<V;i++){

	for(j=0;j<V;j++){

		if(N[i][j]==1){

			for(k=1;k<V;k++){

				if(N[i][k]==1){

						N[j][k]=1;

				}

			}

		}

	}

}

ウォーシャルの方法と呼ばれる