Ver Mensaje Individual
  #24 (permalink)  
Antiguo 08/06/2013, 15:04
Avatar de bulter
bulter
 
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 16 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

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.

Código PHP:
function detectCycle(Node $nodes)
{
    foreach(
$nodes->GetAllChilds() as $node)
    {    
        if(isset(
VisitedNodes::$Nodes[$node->GetValue()]))
        {
            return 
true;
        }
        else
        {            
            
VisitedNodes::$Nodes[$node->GetValue()] = true;
            
            if(
detectCycle($node) == true)
            {
                return 
true;
            }
        }
    }    
}

if(
detectCycle($nodes[1]) == true)
{
    echo 
"Graph";
}
else
{
    echo 
"Tree";

Si quieres dame 10948392835729348720938475 nodos....
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 ?

y por cierto

Cita:
- Un array del tipo <nodo> => <veces que has pasado por el nodo>
Un array del tipo nodo ? eso como se hace?