Detecta ciclos en un gráfico de genealogía durante una búsqueda de profundidad primero

Question

Estoy cargando datos genealógicos del caballo de forma recursiva. 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 dejar de repetirse?

Pensé en que mientras era recurrente mantener una tabla hash con todos los "visitados" caballos. 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

Pseudocó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 por el que ya pasamos, entonces sabe que hemos formado un ciclo (y deberíamos omitir el valor o hacer lo que sea necesario)

Answer 2

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

Cada vez que avanzas hacia abajo en el árbol, escanea la pila en busca del elemento hijo. Si encuentra una coincidencia, entonces ha descubierto un bucle y debe omitir ese elemento secundario. De lo contrario, empuje al niño hacia la pila y continúe. Cada vez que retroceda hacia arriba del árbol, saque un elemento de la pila y deséchelo.

(En el caso de los datos genealógicos, un nodo '' hijo '' en el árbol es presumiblemente el padre biológico del nodo '' padre '').

Answer 3

Esto suena como un caso en el que finalmente puede aplicar esa pregunta de trivia de la entrevista: encuentre un ciclo en una lista vinculada usando solo la memoria O (1).

En este caso, su " lista vinculada " es la secuencia de elementos que enumeras. Use dos enumeradores, ejecute uno a media velocidad, y si el rápido alguna vez se encuentra con el lento, entonces tiene un bucle. Este también será el tiempo O (n) en lugar del tiempo O (n ^ 2) requerido para verificar una lista 'vista'. La desventaja es que solo se entera del ciclo después de que algunos de los nodos se hayan procesado varias veces.

En el ejemplo, he reemplazado el método de 'velocidad media' con el método más simple de escribir 'marcadores de caída'.

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

Answer 4

Una forma muy simple de detectar esto es verificando esa restricción en sí misma:

  

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

Cada vez que inserte un nodo en su árbol, atraviese el árbol hasta la raíz para asegurarse de que el caballo no exista como ningún tipo de padre.

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

Answer 5

Su solución de tabla hash debería funcionar si realiza un seguimiento de los nodos en lugar de los 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 6

Se trata de un gráfico acíclico dirigido , no un árbol. No debería haber ningún ciclo, ya que el descendiente de un caballo no puede ser también su antepasado.

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