¿Cómo puedo detectar la lógica circular o la recursión en referencias y dependencias de varios niveles?

Question

Tengo un gráfico de dependencias de múltiples niveles como este, y necesito detectar cualquier referencia circular en este gráfico.

A = B

B = C

C = [D, B]

D = [C, A]

Alguien tener un problema como este?

¿Alguna solución ???

Gracias y lo siento por el inglés.

========= ========== actualizado

yo tuvimos otra situación.

2 = 1

3 = 2

4 = [2, 3]

5 = 4

En este caso, mi recursiva código iterate dos veces en la referencia "4", pero estas referencias no generan un bucle infinito. Mi problema es saber cuándo la función itera más de una vez una referencia y no es un bucle infinito y cuándo es un bucle infinito, para informar al usuario.

1 = 4

2 = 1

3 = 2

4 = [2, 3]

5 = 4

Este caso es un poco diferent de 2º ejemplo. Esto genera un ciclo infinito. ¿cómo puedo saber cuándo los casos generan un ciclo infinito o no?

Answer 1

Mantenga una lista de nodos identificados de manera única. Intente con recorrer todo el árbol, pero siga revisando los nodos de la lista hasta obtener un nodo que se refiera como un niño que ya está allí en la lista única: tómelo desde allí (maneje el ciclo o simplemente ignórelo según su requisito)

Answer 2

Topological sorting. La descripción en Wikipedia es clara y funciona para todos tus ejemplos.

Básicamente, comienza con un nodo que no tiene dependencias, lo pone en una lista de nodos ordenados y luego elimina esa dependencia de cada nodo. Para el segundo ejemplo, eso significa que comienzas con 1. Una vez que eliminas todas las dependencias en 1, te queda 2. Luego terminas clasificándolos 1,2,3,4,5 y viendo que no hay ciclo.

Para su tercer ejemplo, cada nodo tiene una dependencia, por lo que no hay ningún lugar para comenzar. Tal gráfica debe contener al menos un ciclo.