检查关系传递性的算法？

Question

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

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

我将关系存储为布尔矩阵，如果元素与图表中的0相关，则有1。

谢谢。

Answer 1

拓扑排序或许是正确的方向。 如果有向图表示中没有循环，则该关系是传递的。 如果您关心速度，图算法可能是最佳选择。

Answer 2

尽管这听起来完全像家庭作业...

您需要存储您的关系，以便您可以通过先行词快速查找它们。 然后你就可以发现A->B->C类型的传递关系，将它们添加到同一个存储中，并继续查找A->B->C->D，等等。 。

Answer 3

与我的地图/集合版本（已删除）相比，算法更简单，现在带有布尔矩阵。 也许这更容易理解，即使你不懂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));
  }
}