检查关系传递性的算法？

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-> B-> C的传递关系，将它们添加到相同的存储器，并继续查找A-> B-> C-> D等等。

Answer 3

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