Detectar ciclos en un gráfico de genealogía durante una búsqueda de profundidad en primer lugar

Question

Estoy cargando datos genealógicos de caballo recursivamente. Para algunos conjuntos de datos incorrectos, mi recursión nunca se detiene ... y eso se debe a que hay ciclos en los datos.

¿Cómo puedo detectar esos ciclos para que dejen de repetirse?

Pensé en repetir mientras mantengo un hashTable con todos los caballos "visitados". Pero eso encontrará algunos falsos positivos, porque un caballo PUEDE estar dos veces en un árbol.

Lo que no puede suceder es que un caballo aparezca como padre o abuelo o bisabuelo de SÍ MISMO.

Answer 1

pseudo código:

void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen) 
{ 
    if(seen.Contains(currentNode)) return; 
    // Or, do whatever needs to be done when a cycle is detected 

    ProcessHorse(currentNode.Horse); // Or whatever processing you need 

    seen.Push(currentNode); 

    foreach(GenTreeNode childNode in currentNode.Nodes) 
    { 
     ProcessTree(childNode, seen); 
    } 

    seen.Pop(); 
} 

La idea básica es mantener una lista de todos los nodos que ya hemos visto en nuestro camino hacia el nodo actual; si fue volver a un nodo que ya hemos pasado, entonces usted sabe que hemos formado un ciclo (y debemos omitir el valor, o hacer lo que sea necesario)

Answer 2

Mantiene una pila de todos los elementos que conducen a la raíz del árbol.

Cada vez que avanza por el árbol, escanee la pila para el elemento secundario. Si encuentra una coincidencia, entonces ha descubierto un ciclo y debe omitirlo. De lo contrario, empuje al niño en la pila y continúe. Cada vez que vuelves al árbol, saca un elemento de la pila y deséchalo.

(En el caso de datos genealógicas, un nodo de "niño" en el árbol es presumiblemente el padre biológico del nodo "padre".)

Answer 3

Una forma muy sencilla de detectar esto, es mediante la comprobación de que la restricción sí mismo:

Lo que no puede suceder es que un caballo aparezca como padre o abuelo o bisabuelo de SÍ MISMO.

Siempre que inserte un nodo en su árbol, recorra el árbol hasta la raíz para asegurarse de que el caballo no exista como un tipo de elemento primario.

Para acelerar esto, puede asociar una tabla hash a cada nodo, donde almacena la respuesta en caché de dicha búsqueda. Entonces no tiene que buscar todo el camino la próxima vez que inserte un caballo debajo de ese nodo.

Answer 4

Su solución de tabla hash debería funcionar si usted realiza un seguimiento de los nodos en lugar de caballos. Solo asegúrese de que cada vez que lea un nuevo caballo cree un nuevo nodo incluso si el valor/caballo es el mismo que el valor/caballo de un nodo anterior.

Answer 5

Estás tratando con un directed acyclic graph, no es un árbol. No debería haber ningún ciclo, ya que el descendiente de un caballo tampoco puede ser su antepasado.

Sabiendo esto, debe aplicar técnicas de código específicas para gráficos acíclicos dirigidos.

Answer 6

Esto suena como un caso en el que finalmente puede aplicar la pregunta de preguntas de la entrevista: busque un ciclo en una lista vinculada utilizando solo la memoria O (1).

En este caso, su "lista vinculada" es la secuencia de elementos que enumera.Usa dos enumeradores, ejecuta uno a la mitad de velocidad, y si el rápido alguna vez se encuentra con el lento, entonces tienes un bucle. Este también será el tiempo O (n) en lugar del tiempo O (n^2) requerido para verificar una lista 'vista'. Lo malo es que solo se entera sobre el ciclo después de que algunos de los nodos hayan sido procesados ​​varias veces.

En el ejemplo he reemplazado el método de 'media velocidad' con el método de 'soltar marcadores' más simple de escribir.

class GenTreeNode { 
    ... 

    ///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary> 
    private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) { 
     long cur_track_count = 0; 
     long high_track_count = 1; 
     T post = default(T); 
     foreach (var e in sub_enumerable) { 
      yield return e; 
      if (++cur_track_count >= high_track_count) { 
       post = e; 
       high_track_count *= 2; 
       cur_track_count = 0; 
      } else if (object.ReferenceEquals(e, post)) { 
       throw new Exception("Infinite Loop"); 
      } 
     } 
    } 

    ... 

    ///<summary>Enumerates the tree's nodes, assuming no cycles</summary> 
    private IEnumerable<GenTreeNode> tree_nodes_unchecked() { 
     yield return this; 
     foreach (var child in this.nodes) 
      foreach (var e in child.tree_nodes_unchecked()) 
       yield return e; 
    } 
    ///<summary>Enumerates the tree's nodes, checking for cycles</summary> 
    public IEnumerable<GenTreeNode> tree_nodes() 
    { 
     return CheckedEnumerable(tree_nodes_unchecked()); 
    } 

    ... 

    void ProcessTree() { 
     foreach (var node in tree_nodes()) 
      proceess(node); 
    } 
}