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

Question

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

関係の推移性をチェックするアルゴリズムを提案してください

リレーションをブールマトリックスとして保存しています。グラフのように要素が他の意味で 0 に関連付けられている場合は 1 です。

ありがとう。

Answer 1

Map / Setバージョン（削除済み）よりもはるかに単純なアルゴリズムが、ブール行列になりました。おそらく、Javaを知らなくても、これは理解しやすいでしょうか？

public class Trans
{

  final static int SIZE = 4;

  static boolean isTransitive(boolean[][] function)
  {
    for (int i = 0; i < SIZE; i++)
    {
      for (int j = 0; j < SIZE; j++)
      {
        if (function[i][j])
        {
          for (int k = 0; k < SIZE; k++)
          {
            if (function[j][k] && !function[i][k])
            {
              return false;
            }
          }
        }
      }
    }
    return true;
  }

  public static void main(String[] args)
  {
    boolean[][] function = new boolean[SIZE][SIZE];
    for (int i = 0; i < SIZE; i++)
    {
      function[i] = new boolean[SIZE];
    }
    function[0][1] = true;
    function[1][2] = true;
    function[0][2] = true;
    function[0][3] = true;
    function[1][3] = true;   
    System.out.println(isTransitive(function));
  }
}

Answer 2

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

リレーションシップを保存して、前件でリレーションシップを非常にすばやく検索できるようにする必要があります。その後、タイプA-＆gt; B-＆gt; Cの推移的関係を発見し、それらを同じストレージに追加し、A-＆gt; B-＆gt; C-＆gt; Dなどを引き続き検索できます。 。

Answer 3

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