algorithm - 检查关系传递性的算法？

Question

我需要检查关系是否传递？

您能否建议一些算法来检查关系的传递性？

我将关系存储为布尔矩阵，如果元素相关，则为1 ，否则为0，如图形中。

谢谢。

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->B->C 类型的传递关系，将它们添加到同一个存储中，然后继续查找 A->B->C->D 等...

Answer 3

拓扑排序可能是正确的方向。如果其有向图表示中没有循环，则该关系是可传递的。如果你关心速度，图算法可能是要走的路。