¿Cómo detectar si un gráfico dirigido es cíclico?

Lo que realmente necesitas, creo, es un algoritmo de ordenación topológica como el descrito aquí:

Http://en.wikipedia.org/wiki/Topological_sorting

Si el grafo dirigido tiene un ciclo entonces el algoritmo fallará.

A los comentarios/respuestas que he visto hasta ahora parece que les falta el hecho de que en un gráfico dirigido puede haber más de una forma de pasar del nodo X al nodo Y sin que haya ciclos (dirigidos) en el gráfico.

Utilice DFS para buscar si alguna ruta es cíclica

class Node<T> { T value; List<Node<T>> adjacent;  }

class Graph<T>{

    List<Node<T>> nodes;

   public boolean isCyclicRec()
   {

      for (Node<T> node : nodes)
      {
            Set<Node<T>> initPath = new HashSet<>();
            if (isCyclicRec(node, initPath))
            {
              return true;
            }
      }
      return false;
   }

   private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path)
   {
      if (path.contains(currNode))
      {
        return true;
      }
      else
      {
        path.add(currNode);
        for (Node<T> node : currNode.adjacent)
        {
            if (isCyclicRec(node, path))
            {
                return true;
            }
            else
            {
                path.remove(node);
            }
        }
      }
      return false;
  }

Enfoque: 1
¿qué tal un nivel sin asignación para detectar un ciclo. por ejemplo: considere el gráfico a continuación. A - >(B,C) B->D D->(E,F) E,F->(G) E->D Mientras realiza un DFS comience a asignar un nivel no al nodo que visita (raíz A=0). nivel no del nodo = padre+1. Entonces A = 0, B = 1, D=2, F=3, G=4 entonces, la recursión alcanza D, entonces E=3. No marque el nivel para G (G ya es un nivel no asignado que es mayor que E) Ahora E también tiene una ventaja para D. Por lo que la nivelación diría que D debería obtener un nivel no de 4. Pero D ya tiene un "nivel inferior" asignado a él de 2. Por lo tanto, cada vez que intente asignar un número de nivel a un nodo mientras hace DFS que ya tiene un número de nivel más bajo establecido en él, sabrá que el gráfico dirigido tiene un ciclo..

Approach2:
usar 3 colores. blanco, gris, negro. coloree solo los nodos blancos, los nodos blancos a gris a medida que avanza por el DFS, coloree los nodos grises a negro cuando se despliega la recursividad (se procesan todos los hijos). si no todos los niños todavía procesados y se golpea un nodo gris que es un ciclo. por ejemplo: todo blanco para comenzar en el gráfico directo anterior. color A, B, D,F, G son de color blanco-gris. G es la hoja por lo que todos los niños procesaron color gris a negro. la recursividad se despliega a F (todos los niños procesados) coloreándola de negro. ahora llegas a D, D tiene niños sin procesar, así que color E gris, G ya de color negro, así que no vayas más abajo. E también tiene borde a D, por lo que mientras aún procesa D (D todavía gris), encuentra un borde de nuevo a D(un nodo gris), se detecta un ciclo.

Las pruebas de clasificación topológica sobre el gráfico dado le llevarán a la solución. Si el algoritmo para topsort, es decir, los bordes siempre deben ser dirigidos de una manera falla, entonces significa que el gráfico contiene ciclos.

Otra solución simple sería un enfoque de marcación y barrido. Básicamente, para cada nodo en el árbol lo marca como" visitado " y luego pasa a sus hijos. Si alguna vez ves un nodo con la bandera" visted", sabes que hay un ciclo.

Si no es posible modificar el gráfico para incluir un bit "visitado", se puede usar un conjunto de punteros de nodo en su lugar. Para marcar un nodo como visitado, coloque un puntero a él en el conjunto. Si el puntero ya está en el conjunto, hay un ciclo.