Cita:
Iniciado por bulter Si que te has enganchado con el tema de que si es un arbol o un graph y esos 100 000 nodos.
Si me da 100.000 conexiones de nodos haria una comprobacion para ver si en estas conexiones hay ciclos si hay , es un graph si no , es un arbol asi de simple...... tampoco es gran filosofía.
No..Sólo es una funcion n^2...
Y sólo para saber si es un ciclo o no...Luego tendrás que resolverla...
Cita:
Iniciado por bulter No son ni 4 ni 5 rutas son 9
Código:
7,8,1,5,11,2,15
7,8,4
7,8,6
7,8,1,5,11,3
4,8,1,5,11,2,15
4,8,1,5,11,3
6,8,1,5,11,2,15
6,8,1,5,11,3
15,2,11,3
Aqui ves espejismo ?
No.Veo un ALGORITMO INCORRECTO.
Veo una lista donde sigue faltando la conexión entre 4 y 6, que obviamente EXISTE.Una tercera vez: Falta el camino 4 8 6
Y, entonces tienes 10 caminos, que, oh casualidad, es justo la mitad de 20, que es 5 nodos * 4 caminos por nodo.
Y es justo la mitad, porque en tu lista, aparece el camino de 15 a 3 (empezando por la derecha), pero no aparece el de 3 a 15 (el mismo, "espejado").
Así que, cuando añadas el camino que falta (o, más bien, descubras por qué tu algoritmo no funciona, y está relacionado con una variable miembro que no estás reseteando cuando debes), y así tengas 10 caminos, y luego los vuelvas a escribir otras 10 veces, esta vez de derecha a izquierda, tendrás los 20 caminos, que son exactamente 5 * 4.
Y, sin tanto lío: si 5 ciudades están conectadas por carretera, es obvio que cada ciudad está conectada con otras 4.Amos, creo que es simple esto.Y que si te sale cualquier otra cosa, es que hay algo que falla.