관계의 전이성을 확인하기위한 알고리즘?

Question

관계가 전이적인지 아닌지 확인해야합니까?

관계의 전이성을 확인하기 위해 알고리즘을 제안 하시겠습니까?

나는 관계를 a로 저장하고 있습니다 부울 매트릭스 거기 있습니다 1 요소가 다른 현명한 경우 0 그래프처럼.

감사.

Answer 1

내지도/세트 버전 (삭제)으로 훨씬 간단한 알고리즘, 이제 부울 매트릭스가 있습니다. 자바를 모르더라도 이해하기가 더 쉽습니까?

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

토폴로지 분류는 올바른 방향 일 수 있습니다. 지시 된 그래프 표현에 루프가없는 경우 관계는 전이적입니다. 속도에 관심이 있다면 그래프 알고리즘이 갈 수있는 방법 일 것입니다.