Cómo comprobar si hay un círculo en un árbol?

Question

Aquí es un árbol:

  

  

1. Habrá una raíz.

  

2. Cada nodo del árbol tiene cero o más hijos.

  

3. Se permite que dos nodos puntos al mismo niño. Say, tanto el nodo A   y el nodo B tiene niño C.

  

Sin embargo, se prohíbe que,

  

Nodo A es un descendiente del nodo B, y   Nodo B es un descendiente del nodo A.

Uno de los casos es prohibida

  

nodo A tiene un hijo del nodo C y el nodo D,

     

Tanto el nodo C y D tiene un nodo hijo E,

     

Nodo E tiene un niño de A.

La pregunta es, ¿cómo determinar este círculo de una manera más rápida?

Actualizar : Me doy cuenta de esto es encontrar cualquier ciclo en un grafo dirigido. Justo ahora me las arreglé para pensar en una solución similar al algoritmo de Tarjan.

Gracias por los comentarios.

Answer 1

primera búsqueda en profundidad a través del árbol. Si en algún momento usted encuentra un nodo que ya está en su pila de vuelta hacia atrás, hay un círculo.

Answer 2

Los círculos se pueden encontrar por medio de 2 puntos y avanzar ellas a diferentes intervalos. Finalmente, los punteros coincidirán, lo que indica un bucle, o el "más rápido" uno alcanzarán luego terminar. La pregunta por lo general se le pide a las listas enlazadas, sin embargo, no árboles.