Algorithmus für die Transitivität der Relation Überprüfung?

Question

Ich muss überprüfen, ob Relation transitiv ist oder nicht?

Möchten Sie bitte einige Algorithmus schlagen die Transitivität der Beziehungen zu überprüfen?

Ich bin Speicherung Beziehung als boolean Matrix ist 1 , wenn Elemente andere weist im Zusammenhang 0 wie in Graphen.

Danke.

Answer 1

Viel einfacher Algorithmus wie meine Karte / Set-Variante (gelöscht), jetzt mit boolean Matrix. Vielleicht ist leichter zu verstehen, auch wenn Sie Java nicht kennen?

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

Trotz dieser völlig klingt wie Hausaufgaben ...

Sie müssen Ihre Beziehungen speichern, so dass Sie sie nach oben durch die vorgängigen sehr schnell aussehen können. Dann können Sie transitive Beziehungen vom Typ A-> B-> C, fügen Sie sie auf demselben Speicher entdecken, und halten zu gehen sehen A-> B-> C-> D, etc etc ...

Answer 3

Topologische Sortierung kann die richtige Richtung. Die Beziehung ist transitive wenn es keine Schleifen in ihrer gerichteten Graphen-Darstellung sind. Wenn Sie auf Geschwindigkeit, sind Graphenalgorithmen wahrscheinlich der Weg zu gehen.