algorithm - 関係の推移性をチェックするためのアルゴリズム？

Question

関係が推移的であるかどうかを確認する必要がありますか？

関係の推移性をチェックするためのアルゴリズムを提案していただけますか？

関係をブール行列として格納しています。グラフのように要素が他の方法で関連している場合は1があります。

ありがとう。

Answer 1

これにもかかわらず、完全に宿題のように聞こえます...

先行詞が非常に迅速に検索できるように、関係を保存する必要があります。次に、タイプA-> B-> Cの推移的な関係を検出し、それらを同じストレージに追加して、A-> B->C->Dなどを検索し続けることができます...

Answer 2

トポロジカルソートは正しい方向かもしれません。有向グラフ表現にループがない場合、関係は推移的です。速度が気になる場合は、グラフアルゴリズムが最適です。