Thingmemo
実装一覧へ戻る

グラフ

推移的閉包

Warshall法で有向グラフの隣接行列から到達可能性の推移的閉包を求めます。

TIME
O(V³)
SPACE
O(V²)

V = 頂点数 / 上限: 要素が0または1の1×1〜200×200正方隣接行列、履歴256件まで

隣接行列の推移閉包を求めます。

関連するアルゴリズム