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

Question

¿Cómo podemos detectar si un gráfico dirigido es cíclico? Pensé en usar la primera búsqueda de amplitud, pero no estoy seguro. ¿Algunas ideas?

Answer 1

Por lo general, se utiliza la búsqueda de profundidad en primer lugar. No sé si BFS se aplica fácilmente.

En DFS, se construye un árbol de expansión por orden de visita. Si se visita un ancestro de un nodo en el árbol (es decir, se crea un borde posterior), detectamos un ciclo.

Consulte http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf para una explicación más detallada.

Answer 2

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

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

Answer 3

Lo que realmente necesita, creo, es un algoritmo de clasificación topológica como el que se describe aquí:

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

Si el gráfico dirigido tiene un ciclo entonces el algoritmo se producirá un error.

Los comentarios/respuestas que he visto hasta ahora parecen estar perdiendo el hecho de que en un dirigido gráfico puede haber más de una manera de llegar del nodo X al nodo Y sin que haya (dirigido) ciclos en el gráfico.

Answer 4

aproximación: 1
cómo sobre un nivel no asignación para detectar un ciclo. Ej .: considere el siguiente gráfico. A -> (B, C) B-> D D -> (E, F) E, F -> (G) E-> D A medida que realiza un inicio DFS asignando un nivel no al nodo que visita (raíz A = 0). nivel no de nodo = padre + 1. Entonces A = 0, B = 1, D = 2, F = 3, G = 4 entonces, la recursión llega a D, entonces E = 3. No marque el nivel para G (G ya tiene un nivel no asignado que es más grande que E) Ahora E también tiene una ventaja a D. Así que la nivelación diría que D debería obtener un nivel no de 4. Pero D ya tiene asignado un "nivel inferior" a ella de 2. de este modo cualquier momento se intenta asignar un número de nivel a un nodo mientras se hace DFS que ya tiene un número menor nivel fijado a él, que conoce el gráfico dirigido tiene un ciclo ..

Approach2:
usa 3 colores blanco, gris, negro. coloree únicamente nodos blancos, nodos blancos a gris a medida que baja por el DFS, coloque los nodos grises en negro cuando se desarrolle la recursión (se procesan todos los elementos secundarios). si no todos los niños aún procesados ​​y golpeas un nodo gris, eso es un ciclo. por ej .: todo blanco para comenzar en el gráfico directo de arriba. color A, B, D, F, G son de color blanco grisáceo. G es hoja, por lo que todos los niños procesados ​​lo colorean de gris a negro. la recursividad se desarrolla en F (todos los niños procesados) lo colorean en negro. ahora llegas a D, D tiene niños no procesados, por lo que el color E es gris, G ya es de color negro, así que no vayas más abajo. E también tiene borde a D, por lo tanto, mientras procesa D (D sigue siendo gris), encuentra un borde hacia atrás a D (un nodo gris), se detecta un ciclo.

Answer 5

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

Answer 6

Uso DFS para buscar si cualquier camino es cíclico

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; 
    }