Foros del Web » Programando para Internet » PHP »

Buscar el camino mas largo

Estas en el tema de Buscar el camino mas largo en el foro de PHP en Foros del Web. Hola, necesito su ayuda para resolver el siguiente problema que tengo: Digamos tengo las siguiente conexiones: Cita: 5-11, 1-8, 11-3, 8-7, 1-5, 11-2, 8-6, 2-15, ...

  #1 (permalink)  
Antiguo 07/06/2013, 14:59
 
Fecha de Ingreso: junio-2013
Mensajes: 7
Antigüedad: 6 años, 6 meses
Puntos: 1
Buscar el camino mas largo

Hola,
necesito su ayuda para resolver el siguiente problema que tengo:
Digamos tengo las siguiente conexiones:

Cita:
5-11,
1-8,
11-3,
8-7,
1-5,
11-2,
8-6,
2-15,
8-4
la distancia entre cada es la suma de los 2 es decir la distancia de la conexion 5-11 es 16.
Necesito encontrar cual es la distancia mas larga entre todas las conexiones.
En este caso seria: 7,8,1,5,11,2,15 que es 49.

No puedo dar os codigo por que estoy atascado por completo :( no se ni por donde empezar.
  #2 (permalink)  
Antiguo 07/06/2013, 15:08
Avatar de enlinea777  
Fecha de Ingreso: mayo-2008
Ubicación: frente al pc
Mensajes: 1.830
Antigüedad: 11 años, 6 meses
Puntos: 127
Respuesta: Buscar el camino mas largo

que es estooooooooooooo?
la tarea que dejo el profesor jajajaja
  #3 (permalink)  
Antiguo 07/06/2013, 15:51
Avatar de PIRRUMAN  
Fecha de Ingreso: febrero-2006
Ubicación: Monterrey, Nuevo León
Mensajes: 631
Antigüedad: 13 años, 10 meses
Puntos: 53
Respuesta: Buscar el camino mas largo

podrias empezar explicando mas el caso, cuantos numeros recibes, como los recibes , son fijos, que resultado quieres que te muestre .

si no colocas un codigo unicial es dificl que alguien te de codigo de la nada
__________________
“Prefiero ser un tonto momentaneo que un eterno ignorante”
“¡El éxito es resultado de los aciertos,los aciertos resultado de la experiencia y la experiencia resultado de los errores!”
  #4 (permalink)  
Antiguo 07/06/2013, 15:57
Avatar de wizanchez  
Fecha de Ingreso: junio-2013
Ubicación: bogota
Mensajes: 120
Antigüedad: 6 años, 6 meses
Puntos: 6
Respuesta: Buscar el camino mas largo

- explicate mejor, asi es dificil,
- me hiciste recordar los ejercicios de la U, tiempos aquellos,,
__________________
---------
cubesoftechnology.com
Wizanchez,,
  #5 (permalink)  
Antiguo 07/06/2013, 16:14
 
Fecha de Ingreso: junio-2013
Mensajes: 7
Antigüedad: 6 años, 6 meses
Puntos: 1
Respuesta: Buscar el camino mas largo

No es de la Uni ... por la simple razon, de que no voy a ninguna :D

No son datos fijos, estos numeros son ejemplo con el que necesito trabajar.
Explico 5 esta conectado con 11, por su lado 11 con 2 es decir que 5 esta conectado con 2 tambien. Algo asi:

Código:
      [ 1 ]
       / \
   [ 8 ]  [ 5 ]
   / | \     \ 
[7] [4] [6]   [11]
               | \
	     [2] [3]
	       |
	    [15]
El camino mas largo aqui es empezar por 7 pasar por 8,1,5,11,2 y llegar al 15 ( que la suma total es 7 + 8 + 1 + 5 + 11 + 2 + 15 = 49 ) y es el camino mas largo por que la suma de estos numeros es la mas alta posible. Pues esto es lo que quiero encontrar el camino mas largo segun la distancia ( en el caso 49 ).

La entrada que se recibe son las conexiones
Código:
5-11,
1-8,
11-3,
8-7,
1-5,
11-2,
8-6,
2-15,
8-4
y la salida tiene que ser algo asi:

Cita:
La ruta mas larga es: 7, 8, 1, 5, 11, 2, 15
Con total distancia de: 49
  #6 (permalink)  
Antiguo 07/06/2013, 16:23
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Explicarte mejor en este caso, significaría, sobre todo, en si las conexiones son dirigidas. Es decir, "1-8" significa que hay conexion entre 1 y 8, y entre 8 y 1?
Yo voy a suponer que sí.
En cuyo caso, por ejemplo, hay que tener en cuenta que pueden existir ciclos, o que todo el segmento sea un círculo.
El problema tiene su gracia.Pero tampoco es correcto resolvértelo.Lo primero que tienes que pensar es en algún invariante, algo que siempre sea cierto, y apoyarte en ello.
Una pista : Si vas apuntando qué números vas usando en el recorrido, ningún número puede aparecer más de 2 veces.
Cita:
que es estooooooooooooo?
la tarea que dejo el profesor jajajaja
Es mucho mejor ayudar a alguien que aprende, que a mucha gente que pregunta trivialidades muchisimo mayores y están cobrando por programar "profesionalmente".
  #7 (permalink)  
Antiguo 07/06/2013, 16:29
 
Fecha de Ingreso: junio-2013
Mensajes: 7
Antigüedad: 6 años, 6 meses
Puntos: 1
Respuesta: Buscar el camino mas largo

dashtrash si. Si 1 esta conectado con 8 entonces 8 estara conectado con 1.
Me podriais dar algo para leer o no se.... pero no me entero de esto :(
Lo primero que pienso que estaria bien hacer es que de alguna manera me guarde todas las conexiones ... pero no se me ocurre nada listo.. lo mejor que se me ha ocurrido es:

Código PHP:
$connection[5] = 11;
$connection[1] = 8;
$connection[11] = 3
pero con 11-2 la 3 desaparecera.
  #8 (permalink)  
Antiguo 07/06/2013, 16:32
Avatar de pateketrueke
Modernizr
 
Fecha de Ingreso: abril-2008
Ubicación: Mexihco-Tenochtitlan
Mensajes: 26.399
Antigüedad: 11 años, 8 meses
Puntos: 2534
Respuesta: Buscar el camino mas largo

Me suena a que usando algo de base de datos podrías relacionar todo de manera eficiente.
__________________
Y U NO RTFM? щ(ºдºщ)

No atiendo por MP nada que no sea personal.
  #9 (permalink)  
Antiguo 07/06/2013, 16:34
 
Fecha de Ingreso: junio-2013
Mensajes: 7
Antigüedad: 6 años, 6 meses
Puntos: 1
Respuesta: Buscar el camino mas largo

oO base de datos para que , no le veo el sentido de usar DB en este problema mio
  #10 (permalink)  
Antiguo 07/06/2013, 16:43
Avatar de PIRRUMAN  
Fecha de Ingreso: febrero-2006
Ubicación: Monterrey, Nuevo León
Mensajes: 631
Antigüedad: 13 años, 10 meses
Puntos: 53
Respuesta: Buscar el camino mas largo

suponiendo que el primer valor es el padre y el segundo es su hijo...
parte de un algoritmo seria:
---iniciar una variable a cero
---encontrar los numeros que no tengan hijos
---sumar a tu variable el hijo encontrado
---con cada numero encontrado buscar el padre de este numero
---sumar el padre a tu varible
---buscar si el primer padre tiene hijos
---si tiene hijos sumar a tu variable
...
---llegar a un numero que no tiene hijos
--sumar y guardar el resultado
---recorrer el arbol por otro camino
---comparar y almacenar el resultado mayor

... la idea es recorrer los posibles caminos del arbol armado e ir sumando los nodos comparando con resultados anteriores
__________________
“Prefiero ser un tonto momentaneo que un eterno ignorante”
“¡El éxito es resultado de los aciertos,los aciertos resultado de la experiencia y la experiencia resultado de los errores!”
  #11 (permalink)  
Antiguo 07/06/2013, 16:47
Avatar de jcxnet  
Fecha de Ingreso: octubre-2005
Ubicación: Perú
Mensajes: 784
Antigüedad: 14 años, 2 meses
Puntos: 56
Respuesta: Buscar el camino mas largo

es un típico caso para aplicar nodos y grafos
__________________
►I'm a devil on the run ♂
Jcxnet.com
*Keep It Simple **
  #12 (permalink)  
Antiguo 07/06/2013, 16:55
Avatar de wizanchez  
Fecha de Ingreso: junio-2013
Ubicación: bogota
Mensajes: 120
Antigüedad: 6 años, 6 meses
Puntos: 6
Respuesta: Buscar el camino mas largo

- es una recusrsividad , ta arrecho mano
__________________
---------
cubesoftechnology.com
Wizanchez,,
  #13 (permalink)  
Antiguo 07/06/2013, 18:48
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Lo pintas como un árbol..pero en tu planteamiento, no hay nada que diga que es un árbol.Pueden ser varios grafos no conectados entre sí.En tu planteamiento no se puede suponer que algún nodo es una "raíz" (por donde empezaría facilmente una función recursiva).

Suponiendo que tenemos un camino actual (que tiene 1 segmento intermedio, o varios), vas a necesitar:
- los nodos extremos del camino actual
- la lista **completa** de los segmentos
- Un array del tipo <nodo> => <veces que has pasado por el nodo>
- Un array de índices a los segmentos ya incluidos en el camino actual.

Con eso ya tienes para declarar la función.Para almacenar la lista de segmentos, yo usaría un array de arrays.
  #14 (permalink)  
Antiguo 07/06/2013, 20:02
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por pateketrueke Ver Mensaje
Me suena a que usando algo de base de datos podrías relacionar todo de manera eficiente.
... DB? para que ?

enlinea777 acumulas comentarios insignificantes ?
dashtrash nada mas dibujarte los numeritos dados puedes ver que es un general tree no dirigido ( entonces tanto el padre puede ir al hijo como el hijo al padre ).

Bueno no soy el gran Picaso :D asi que no os riáis de mis PAINT habilidades/skills :D
Para que consigas hacer lo que quieres es fundamental que entiendas la teoria basica de los arboles ( Trees / ADT Tree ). Intentare explicar un poco, con los datos que diste y la ruta que buscas.



Este es tu arbol. En primer lugar dire algunos de los elementos que contiene un arbol ( ya los he escrito en la imagen pero los explicare aqui tambien)

Height: Es la altura del arbol. Empezando desde el primer elemento ( root ) hasta llegar al mas bajo ( 15 ) este arbol tiene un Height ( altura ) = 5

Vertices/Nodes: Son las unidades de las que esta formado el arbol. En este arbol tienes 10 vertices que son: 1,8,5,7,4,6,11,2,3,15

Edges: ( creo que en español se llaman aristas ) Bueno los edges se representan con una linea que une dos nodos/vertices. Si el arbol o el graph es dirigido al edge se le añade una flechita con el destino por ejemplo:

Código:
1: [ N1 ] <------ [ N2 ]
2: [ N1 ] ------> [ N2 ]
3: [ N1 ] <------> [ N2 ]
4: [ N1 ] ------ [ N2 ]
En el caso 1 N2 puede ir a N1, pero N1 no puede ir en N2 ( Esto seria un graph/tree DIRIGIDO )
En el caso 2 N1 puede ir a N2, pero N2 no puede ir en N1 ( Esto seria un graph/tree DIRIGIDO )
En el caso 3 N1 puede ir a N2, igual que N2 a N1 ( Esto seria un graph/tree DIRIGIDO )
En el caso 4 cuando no tienes flechas se entiende que N1 puede ir a N2, igual que N2 a N1 esto seria un graph/tree NO DIRIGIDO.

La cantidad de los edges es siempre VERTICES - 1 (v-1), en este caso 10-1 = 9

Root: o raíz es el elemento que NO tiene parent/padre en este caso 1.
En un arbol o Graph puede haber mas de 1 root pero en este caso tenemos 1 que es mejor por que si son mas las cosas se complican.
Si tienes las conexiones el root seria el numero que NUNCA aparece en la parte derecha. Por ejemplo tus datos:

Código:
5-11,
1-8,
11-3,
8-7,
1-5,
11-2,
8-6,
2-15,
8-4
El unico numero que no esta en la parte derecha es el 1, asi que seria el root de tu arbol. Si digamos añades otra pareje: 20-19 tendrias otro root 20, y otro arbol. Entonces tendras 2 arboles y 1 bosque.

Child: o hijos son aqullos vertices/nodos que tienen parent/padre aqui childs de 1 son 8 y 5 childs de 8 son 7,4,6

Parent: Son los nodos/vertices que tienen 1 o mas childs/hijos. En este caso el parent de 15 seria 2.

Leaf: u Hoja. Cada arbol tiene que tener sus hojas :P. Hoja es el nodo/vertice que no tiene hijos. En este caso Leafs serian: 7,4,6,15,3

Ancestor: Son todos los nodos/vertices que tiene un nodo por encima ( de los que proviene ) es decir los Ancestors de 7 son 8 y 1

Successors: Son todos los nodos que provienen de otro. Es decir los Successors de 11 son 2,3,15, de 1 serian 8,5,7,4,6,11,2,3,15

Siblings: Son todos los nodos que tienen el mismo parent/padre. Por ejemplo en este arbol tenemos 8 y 5 son siblings por que tienen 1 de parent. 7,4,6 son siblings por que los 3 tienen 8 de parent etc.

Depth/Level: o profundidad de un nodo es la longitud de la trayectoria desde la raiz/root hasta el nodo. Es decir el 15 esta el la profundidad/Depth 4. ( El root es 0 ). Bueno de aqui podemos sacar una conclusión que el Height de un arbol es igual a (Depth + 1)

Subtree: Dado un arbol y un nodo digamos "X" el conjunto de todos los nodos/vertices que tienen el nodo "X" como ancestor/ancestro representa una estructura de arbol, lo que se llama subtree o sub-arbol enraizado/rooted en "X". En este arbol podemos decir que 8 es un subtree igual que 11.

Cada nodo en un arbol puede ser alcanzado empezando por su raiz, siguiendo los aristas/edges. La secuencia de edges travesados para llegar de la raiz al nodo "X" se llama Path/Ruta en el arbol. Al contrario que en un graph en un arbol hay solo 1 ruta de la raiz al nodo "X".



Otra vez mis habilidades de Picaso :D

En la primera parte de la imagen muestro que es la Ruta ( path ), bueno esto no tiene mucho que explicar, lo explique en el dibujito.
Bue, bueno aver si lo explicao con un ejemplo asi se queda mas claro.
la parte que dice "Equivalente, p es secuencia de edges e1,...,en donde para i = 2...n edges ei-1 y ei comparten nodo" ( en el dibujo me acabo de dar cuenta que he puesto ei1 en lugar de ei-1)
esto significa que entre EDGE 1 y EDGE 2 se encuentra el mismo NODO

Código:
[ N1 ] ==edge 1== [ N2 ] ==edge 2== [ N3 ] == edge 3 == [ N4 ]
Como se ve aqui edge 2 y su correspondiente edge 2-1 que es el edge 1 tiene el mismo nodo N2

La segunda parte si que puedo añadir que en el arbol que dibuje de ejemplo tiene un tamaño de 11, Ya que tiene 6 nodos y 5 edges. Se puede usar tambien una formula asi: Gsize = (V*2)-1 en nuestro caso ( de la imagen ) seria Gsize = (6*2)-1 = 11

Otra forma por la cual podrias representar tus conexiones seria mediante Adjacency Matrix:



Creas una matriz/array y pones tantos elementos el numero mas grande en tu conexion ( en el caso 15 )
El Adj Matrix ( le llamare A para escribir menos :D ) tiene un tamaño NxN en el caso 15 x 15

Esto en PHP seria muy facil de realizar:

Código PHP:
<?php
$adjMatrix 
= array();

for(
$i 1$i <= 15$i++)
{
    for(
$x 1$x <= 15$x++)
    {
        
$adjMatrix[$i][$x] = false;
    }
}

$adj[1][5] = true;
$adj[1][8] = true;
$adj[5][11] = true;
$adj[8][4] = true;
$adj[8][6] = true;
$adj[8][7] = true;
$adj[11][2] = true;
$adj[11][3] = true;
$adj[2][15] = true;

?>
Solo mencionare las A no voy a explicar mas profundo, pero se pueden usar para mas cosas. ^^

Bueno ... dare ahora un ejemplo como podemos construir un pequeño arbol en PHP ( me vendria mejor C# o C++ pero estamos en la seccion PHP asi que :) ):

Código PHP:
<?php
class Node
{
    private 
$value null;
    private 
$childrens = array();
    private 
$hasParent false;
    
    public function 
__construct($value)
    {
        if(!
is_integer($value))
        {
            throw new 
InvalidArgumentException();
        }
        
        
$this->value $value;
    }
    
    public function 
GetValue()
    {
        return 
$this->value;
    }
    
    public function 
AddChild(Node $child)
    {
        
$child->HasParent(true);
        
$this->childrens[] = $child;
    }
    
    public function 
NumberOfChildrens()
    {
        return 
count($this->childrens);
    }
    
    public function 
GetChild($index)
    {
        if(!
is_integer($index))
        {
            throw new 
InvalidArgumentException();
        }
        
        if(
$index || $index count($this->childrens) || !array_key_exists($index$this->childrens))
        {
            throw new 
OutOfRangeException();
        }
        
        return 
$this->childrens[$index];
    }
    
    public function 
HasParent($hasParent)
    {
        if(
$hasParent != true)
        {
            
$this->hasParent false;
        }
        
        
$hasParent true;
    }
}
?>
Bueno es mas o menos :P
Ahora digamos que quiere crear tu arbol, puede hacer se de esta forma ( la complicada, larga etc. )

Código PHP:
<?php
$root 
= new Node(1);
$child8 = new Node(8);
$child5 = new Node(5);
$child7 = new Node(7);
$child4 = new Node(4);
$child6 = new Node(6);
$child11 = new Node(11);
$child2 = new Node(2);
$child3 = new Node(3);
$child15 = new Node(15);

$root->AddChild($child8);
$root->AddChild($child5);
$child8->AddChild($child7);
$child8->AddChild($child4);
$child8->AddChild($child6);
$child5->AddChild($child11);
$child11->AddChild($child2);
$child11->AddChild($child3);
$child2->AddChild($child15);
?>
Aqui por ejemplo de forma facil podemos sacar los childres de un parent:

Código PHP:
for($i 0$i <= $child11->NumberOfChildrens() - 1$i++)
{
    echo 
$child11->GetValue() . " has " $child11->GetChild($i)->GetValue() . " as child<br />";

cuyo resultado seria:

Cita:
11 has 2 as child
11 has 3 as child
Ahora una forma mucho mas facil de crear este arbol sin definir 1 000 000 de variables seria:

Código PHP:
$entry "5-11,1-8,11-3,8-7,1-5,11-2,8-6,2-15,8-4";
$connections explode(","$entry);
$nodes = array();

foreach(
$connections as $connection)
{
    
$connection explode("-"$connection);
    
    
$parent $connection[0];
    
$child $connection[1];
    
    
$parentNode null;
    
$childNode null;
    
    if(
array_key_exists($parent$nodes))
    {
        
$parentNode $nodes[$parent];
    }
    else
    {
        
$parentNode = new Node((int)$parent);
        
$nodes[$parent] = $parentNode;
    }
    
    if(
array_key_exists($child$nodes))
    {
        
$childNode $nodes[$child];
    }
    else
    {
        
$childNode = new Node((int)$child);
        
$nodes[$child] = $childNode;
    }
    
    
$parentNode->AddChild($childNode);
    
$childNode->AddChild($parentNode);

Como ves aqui

Código PHP:
$parentNode->AddChild($childNode);
$childNode->AddChild($parentNode); 
Indico que puedes ir del parend al child igual que del child al parent

Cita:
3: [ N1 ] <------> [ N2 ]
4: [ N1 ] ------ [ N2 ]
Ahora digamos si quieres tomar TODOS los nodos podrias hacer esto:

Código PHP:
foreach($nodes as $node)
{
    echo 
$node->GetValue() . ", ";

Si quieres tomar solo los leafs/hojas:

Código PHP:
foreach($nodes as $node)
{
    if(
$node->NumberOfChildrens() == 1)
    {
        echo 
$node->GetValue() . " is leaf<br />";
    }

Aqui comprobamos si el nodo tiene hijos, si no tiene, es una hoja/leaf.
Etc.

Bueno lo dejo hasta aqui luego continuare. Si alguno se interesa lo que sigue para resolver este problema es DFS o BFS. Mas tarde explicare como funcionan y como se podra hacer la busqueda de la ruta mas larga en un arbol.
Espero haber ayudado a alguien con esto.

Saludos

Última edición por bulter; 07/06/2013 a las 21:54
  #15 (permalink)  
Antiguo 08/06/2013, 10:00
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

Bueno, aver si llego a terminar :|
Para travesar un arbol/graph existen varios algoritmos unos entre ellos son DFS y BFS, ahora explicare/usare el DFS.

DFS o Depth-First Search. Como el nombre lo dice busca en profundidad. Lo primero que visita son los descendentes de un nodo y al final el nodo. De normal se implementa mediante recursiones.
El pseudo code del DFS seria:

Código:
DFS(node)
{
    for each child c of node
        DFS(c);
    print the current node;
}
El DFS lo que hara es que empezara por las Hojas ( en el caso 7,4,6 ) pasar por todos los Siblings y llagar al padre luego pasara por la otra hoja ( que es 3 ) y de esta a la otra que es 15 luego subira hacia arriba pasando por 2 , 11 y 5

Dare un ejemplo mas sencillo para que se entienda mejor:

(Me picaso)



Cual seria el resultado de esta Graph si lo travesamos con DFS ?!
El algoritmo empezara por el 1 vera que el uno tiene hijos ( 2, 6, 7 ), bajara al 2, vera que el tambien tiene hijos y bajara al 3. Como 3 no tiene hijos daria Output 3 ( print 3 .. etc. ) como 3 no tiene hijos ( es hoja ) volvera hacia arriba ( al padre ). Como 2 tiene otro hijo, bajaremos otra vez, en esta caso seria el 4, dariamos Output 4. Como 4 es una hoja volveriamos arriba al padre, el 2, y bajaremos al otro hijo, el 5, otra vez damos output 5 y volvemos al padre. Ya que 2 no tiene mas hijos damos Output 2 y volvemos al padre , que ahora es el 1, que por su parte tiene otro hijo, el 6. Bajamos al 6 y como es hoja, output 6. Volvemos al 1 bajamos al 7 y del 7 al 8, como 8 es hoja .. output 8, retrocedemos al 7 y como tiene otro hijo , bajamos y damos Output 9 volvemos hacia arriba y como 7 no tiene otro hijo damos output 7 volvemos hasta arriba del todo y como el 1 no tiene mas hijos lo imprimimos ( output 1 ) el resultado final de este arbol travesado seria:

Código:
3,4,5,2,6,8,9,7,1
Un ejemplo de codigo DFS en PHP podria ser:

Código PHP:
function DFS(Node $nodes)
{
    foreach(
$nodes->GetAllChilds() as $node)
    {
        
DFS($node);
        echo 
"Visiting Node: " $node->GetValue() . "<br />";
    }    
}

DFS($nodes[1]); 
El resultado de tu arbol seria:

Cita:
Visiting Node: 7
Visiting Node: 6
Visiting Node: 4
Visiting Node: 8
Visiting Node: 3
Visiting Node: 15
Visiting Node: 2
Visiting Node: 11
Visiting Node: 5
  #16 (permalink)  
Antiguo 08/06/2013, 10:22
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

Y nada, practicamente ya esta el problema resuelto.
Haces un DFS a tu arbol y para cada nodo sumas su valor.
Un camino largo seria de Hoja a Hoja. Entonces empezaras de una hoja hasta llegar a otra si la suma es superior a la que tienes la guardas, si no sigues.

En este arbol en concreto pasaria lo siguiente:
Haras un DFS solo a las hojas y pasaras por todos sus caminos de salida es decir:

Cita:
3, 11, 5, 1, 8, 7, 6, 4, 2, 15
7, 8, 1, 5, 11, 3, 2, 15, 6, 4
6, 8, 1, 5, 11, 3, 2, 15, 7, 4
15, 2, 11, 5, 1, 8, 7, 6, 4, 3
4, 8, 1, 5, 11, 3, 2, 15, 7, 6

-------------------------

[3][3, 11][3, 11, 5][3, 11, 5, 1][3, 11, 5, 1, 8][3, 11, 5, 1, 8, 7][3, 11, 5, 1, 8, 6][3, 11, 5, 1, 8, 4][3, 11, 2][3, 11, 2, 15]

[7][7, 8][7, 8, 1][7, 8, 1, 5][7, 8, 1, 5, 11][7, 8, 1, 5, 11, 3][7, 8, 1, 5, 11, 2][7, 8, 1, 5, 11, 2, 15][7, 8, 6][7, 8, 4]

[6][6, 8][6, 8, 1][6, 8, 1, 5][6, 8, 1, 5, 11][6, 8, 1, 5, 11, 3][6, 8, 1, 5, 11, 2][6, 8, 1, 5, 11, 2, 15][6, 8, 7][6, 8, 4]

[15][15, 2][15, 2, 11][15, 2, 11, 5][15, 2, 11, 5, 1][15, 2, 11, 5, 1, 8][15, 2, 11, 5, 1, 8, 7][15, 2, 11, 5, 1, 8, 6][15, 2, 11, 5, 1, 8, 4][15, 2, 11, 3]

[4][4, 8][4, 8, 1][4, 8, 1, 5][4, 8, 1, 5, 11][4, 8, 1, 5, 11, 3][4, 8, 1, 5, 11, 2][4, 8, 1, 5, 11, 2, 15][4, 8, 7][4, 8, 6]
Como tenemos 5 hojas tendramos 5 posibles caminos y en cada camino unas cuantas variaciones.
Digamos la hoja 3. Tenemos los caminos: [3, 11, 2, 15], [3, 11, 5, 1, 8, 7], [3, 11, 5, 1, 8, 6][3, 11, 5, 1, 8, 4] esos son los 4 caminos mas largos de la hoja 3. Bueno y de aqui ya seria cojer el camino mas largo.
Un codigo que se podria utilizar seria:

Código PHP:
<?php
class NodePaths
{
    private 
$VisitedNodes = array();
    private 
$MaxSum 0;
    private 
$nodeList = array();
    private 
$longestPath "";
    
    public function 
__construct(array $nodes)
    {
        
$this->nodeList $nodes;
    }
    
    public function 
GetLongestPath()
    {
        foreach(
$this->nodeList as $node)
        {
            if(
$node->NumberOfChildren() == 1)
            {
                
$this->VisitedNodes = array();
                
$this->LongestPathDFS($node0);
            }
        }
        
        return array(
"MaxSum" => $this->MaxSum"MaxPath" => $this->longestPath);
    }
    
    private function 
LongestPathDFS(Node $node$currentSum$path "")
    {
        
$this->VisitedNodes[] = $node->value;
        
$currentSum += $node->value;
        
$path = (empty($path)) ? $node->value $path ", " $node->value;
        
        
        for(
$i 0$i $node->NumberOfChildren(); $i++)
        {
            if(
in_array($node->GetNode($i)->value$this->VisitedNodes))
            {
                continue;
            }
            
            
$this->LongestPathDFS($node->GetNode($i), $currentSum$path);
        }
        
        if(
$node->NumberOfChildren() == && $currentSum $this->MaxSum)
        {
            
$this->MaxSum $currentSum;
            
$this->longestPath $path;
        }
    }
}


$path = new NodePaths($nodes);
$pathResult $path->GetLongestPath();

echo 
"Max Path: " $pathResult["MaxPath"] . "(" $pathResult["MaxSum"] . ")<br />";
?>
Espero haber me explicado bien :D si hay dudas pregunta :)
  #17 (permalink)  
Antiguo 08/06/2013, 10:30
 
Fecha de Ingreso: junio-2013
Mensajes: 7
Antigüedad: 6 años, 6 meses
Puntos: 1
Respuesta: Buscar el camino mas largo

o.O Me parece algo complicado. Pero lo has explicado bastante detallado, gracias :) Se me aclararon muchas cosas e intentare seguir de aqui por mi cuenta.
  #18 (permalink)  
Antiguo 08/06/2013, 13:10
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por bulter Ver Mensaje
dashtrash nada mas dibujarte los numeritos dados puedes ver que es un general tree no dirigido ( entonces tanto el padre puede ir al hijo como el hijo al padre ).
Anda..Y tú tomas un caso particular, el de esos "numeritos", para resolver un problema general?
Cuando, en vez de 8 o 9 relaciones, tengas 100000, primero dibujas los 100000 segmentos, y, si ves que es un árbol, entonces aplicas la algoritmia...
En ningún lado se dice que tenga que ser un árbol.En ningún lado se dice siquiera que los segmentos sean conexos.
A partir de ahí , toda la profusa explicación de búsqueda en profundidad, (innecesaria para una cosa tan trivial), es la solución a un problema mal interpretado.
Vuelve al planteamiento del problema.Primer post.
Fácilmente te doy una lista de conexiones de números que forman un ciclo.
Qué ocurriría en ese caso?
Cita:
En un arbol o Graph puede haber mas de 1 root pero en este caso tenemos 1 que es mejor por que si son mas las cosas se complican.
Ah,si? Sólo tenemos uno? Cuál? En la exposición inicial, cuál es el root? Que el OP lo haya querido dibujar de una cierta forma, no es más que una posibilidad entre muchas.

Cita:
Si tienes las conexiones el root seria el numero que NUNCA aparece en la parte derecha. Por ejemplo tus datos:
Cosa que presupones, porque piensas que es un árbol.Pero, como pregunté previamente, las conexiones NO son dirigidas, así que no puedes hacer esa presuposición.Que el root del arbol es el que "NUNCA" aparece en la parte derecha es absurdo.CUALQUIER nodo puede ser el root.Esa presuposición que haces no es cierta.E independientemente de cuál fuera el root, el resultado es el mismo.

Última edición por dashtrash; 08/06/2013 a las 13:22
  #19 (permalink)  
Antiguo 08/06/2013, 14:52
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por bulter Ver Mensaje
Como tenemos 5 hojas tendramos 5 posibles caminos y en cada camino unas cuantas variaciones.
Digamos la hoja 3. Tenemos los caminos: [3, 11, 2, 15], [3, 11, 5, 1, 8, 7], [3, 11, 5, 1, 8, 6][3, 11, 5, 1, 8, 4] esos son los 4 caminos mas largos de la hoja 3. Bueno y de aqui ya seria cojer el camino mas largo.
Si por caminos te refieres distintas parejas nodo de inicio-nodo de fin, como tienes 5 "hojas", tienes 4 caminos.No 5.Todo eso, suponiendo que es un árbol.
Y, obviamente, el camino más largo del nodo x al nodo y, es el mismo que el camino más largo del nodo y al nodo x.El algoritmo no tiene en cuenta esto, y calcula ambos.Es una solución poco eficiente.
  #20 (permalink)  
Antiguo 08/06/2013, 14:54
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

dashtrash Te lo tomas muy a dentro... Que otra cosa sera si no un arbol ... ? No puede ser un graph de ninguna manera ( teniendo estos numeros ) lo planteas como lo planteas teniendo estas mismas relaciones ( ni 1 mas ni 1 menos ) es un arbol ( si pones alguna pareja mas si que lo podras convertir en un Graph, pero yo hablo de los numeros dados )

Cita:
Que el root del arbol es el que "NUNCA" aparece en la parte derecha es absurdo.CUALQUIER nodo puede ser el root
Cualquier nodo puede ser root ? Explicame como podra ser root el 7 si ablamos de 1 arbol y no de Forest ?! oO
  #21 (permalink)  
Antiguo 08/06/2013, 14:57
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

http://www.forosdelweb.com/f18/busca...7/#post4446220

En este comentario hasta Xpozed dibujo el arbol... y se ve claramente que es un arbol y no un graph
Otra cosa ... Una diferencia fundamental entre un arbol y un graph es que el nodo de un arbol puede tener 1 y solo 1 padre, en este yo no veo 2 padres para un nodo oO

Cita:
Cuando, en vez de 8 o 9 relaciones, tengas 100000, primero dibujas los 100000 segmentos, y, si ves que es un árbol,
El caso es de 9 o 19 relaciones y no de 100000, asi que tampoco me costo tanto.

Cita:
5 "hojas", tienes 4 caminos.No 5.
LOL gracias por corregirme, esto si que lo tengo mal , pero tu tambien.
Hay 9

Cita:
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
Asi que supongo ( no lo se seguro ) que el numero de rutas posibles seria Paths=(|V|-1) or Paths=|E|

Cita:
Y, obviamente, el camino más largo del nodo x al nodo y, es el mismo que el camino más largo del nodo y al nodo x.El algoritmo no tiene en cuenta esto, y calcula ambos.Es una solución poco eficiente.
Y obviamente no voy a perder tiempo en perfeccionar una clase/función , para dar un simple ejemplo :@ Poca gracia .....

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?

Última edición por bulter; 08/06/2013 a las 15:27
  #22 (permalink)  
Antiguo 08/06/2013, 15:36
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por bulter Ver Mensaje
dashtrash Te lo tomas muy a dentro... Que otra cosa sera si no un arbol ... ? No puede ser un graph de ninguna manera ( teniendo estos numeros ) lo planteas como lo planteas teniendo estas mismas relaciones ( ni 1 mas ni 1 menos ) es un arbol ( si pones alguna pareja mas si que lo podras convertir en un Graph, pero yo hablo de los numeros dados )
Ah..Que tú estás resolviendo el *caso especifico* de estos numeros..Primero los "pintas", y luego haces un algoritmo...Bueno..Ya que es para estos números especificos, una vez "pintados", es bastante fácil , con el boli, así a ojo, dar la respuesta...no necesitas 3 posts con diagramas, ni ningún algoritmo..
Amos, yo no he visto en mi vida 1 algoritmo para "unos numeros dados".
Repito: si la "lista dada" fuera de 100.000 nodos, primero los pintarias, y luego escribirias un algoritmo dependiendo de lo que "vieras" en tu dibujo?
Cita:
Cualquier nodo puede ser root ? Explicame como podra ser root el 7 si ablamos de 1 arbol y no de Forest ?! oO
Ve a tu dibujo de más arriba, e imagínate que tiras del 7 hacia arriba, hasta que esté mas arriba del 1. Ya es el 7 el root. Si *NO* hay dirección, si no hay ninguna semántica de qué son los nodos, y la posición de los nodos en el arbol no significa "nada", es obvio que dado cualquier conjunto de nodos conectados, puedes "dibujar" arriba de todos a cualquiera de ellos, y dibujar al resto debajo.Esto es una obviedad.
Cita:
LOL gracias por corregirme, esto si que lo tengo mal , pero tu tambien.
No.Lo que has hecho, es eliminar los caminos espejo.Que de A a B, el camino es el mismo que el de B a A.
Explícame cómo es posible que en un árbol conexo, no haya una forma de llegar desde un nodo, sea hoja o no, a cualquier otro nodo.
O sea, cómo es posible que desde una hoja, no exista un camino a cualquier otra hoja.
O sea, que si hay 5 hojas, no haya al menos 4 caminos que conecten cada hoja a las otras 5.
Por eso, que es lógica pura, en tu lista de "soluciones", si contamos cuantas veces
aparece cada número en el extremo derecho o izquierdo de la lista, deberían ser exactamente 4 veces por número.
Pero, por ejemplo el numero "4" no sale 4 veces.Sale 3.
Las hojas que existen son: 7,4,6,15 y 3
El "4", en tus soluciones , sale unido al 15 , al 3 y al 7. Al 6 no.
Usando sólo la lógica, y dado el dato de que hablamos de un árbol, que es conexo, ya te digo que eso significa que tu algoritmo está MAL.
Ahora puedes ir al dibujo...hay un camino del 4 al 6? Yo diría que si...
  #23 (permalink)  
Antiguo 08/06/2013, 16:01
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por bulter Ver Mensaje
http://www.forosdelweb.com/f18/busca...7/#post4446220

En este comentario hasta Xpozed dibujo el arbol...
Y como ya dije, porque le dió por ese dibujo.Podría haber hecho cualquier otro, y presuponer eso es un error.

Cita:
Iniciado por bulter Ver Mensaje
y se ve claramente que es un arbol y no un graph
Ah, si? Cuál es la diferencia?"Se ve"?Qué expresión más técnica...Se "ve" porque ha elegido pintar las líneas con un cierto ángulo? Y si variamos el ángulo? Cambia algo? Se rompe alguna condición del problema?Algoritmicamente, cómo se define "se ve"?

Cita:
Iniciado por bulter Ver Mensaje
Otra cosa ... Una diferencia fundamental entre un arbol y un graph es que el nodo de un arbol puede tener 1 y solo 1 padre, en este yo no veo 2 padres para un nodo oO
Lo que en realidad estás diciendo, es que la diferencia entre un árbol y un graph, es cómo lo pintas.Pero, mientras el ángulo de las líneas que dibujes no sea parte de la definición del problema, es algo que puedes pintar como quieras.Prueba a pintar ángulos de 90 grados en vez de 180 para el primer hijo, por ejemplo.

La diferencia fundamental entre un árbol y un graph, es que el árbol tiene un *criterio de ordenación*.Y, dado ese criterio, la raíz es una, y sólo puede ser esa.
Los nodos se han añadido según un cierto criterio.Sea porque se use en un algoritmo de ordenación, o sea porque es un arbol tipo "categorias",sea por lo que sea, el nodo raíz tiene un significado semántico que hace que sea el raíz.Por ejemplo, en un árbol de categorías, se cumple que los nodos hijos están semánticamente incluidos en su nodo padre (las categorias hijas pertenecen a la categoría padre).

Cita:
Iniciado por bulter Ver Mensaje
El caso es de 9 o 19 relaciones y no de 100000, asi que tampoco me costo tanto.
Juas

Cita:
Iniciado por bulter Ver Mensaje
Un array del tipo nodo ? eso como se hace?
En la expresión array(<nodo>=><veces que se pasa por el nodo>), tanto una cosa como la otra, significa "representación de".Obviamente, no puedes poner un nodo en un array.Ni tampoco puedes poner las sentencias ejecutadas por el ordenador en la iteración por la que pasó por dicho nodo, que es lo que significa "vez que se pasó por el nodo".
Es muy sencillo.Cuando se pasa por el nodo "4" un numero de veces "2", el array es array("4"=>2).
  #24 (permalink)  
Antiguo 08/06/2013, 16:04
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 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?
  #25 (permalink)  
Antiguo 08/06/2013, 16:21
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por bulter Ver Mensaje
http://www.forosdelweb.com/f18/busca...7/#post4446220

En este comentario hasta Xpozed dibujo el arbol...
Y como ya dije, porque le dió por ese dibujo.Podría haber hecho cualquier otro, y presuponer eso es un error.

Cita:
Iniciado por bulter Ver Mensaje
y se ve claramente que es un arbol y no un graph
Ah, si? Cuál es la diferencia?"Se ve"?Qué expresión más técnica...Se "ve" porque ha elegido pintar las líneas con un cierto ángulo? Y si variamos el ángulo? Cambia algo? Se rompe alguna condición del problema?Algoritmicamente, cómo se define "se ve"?

Cita:
Iniciado por bulter Ver Mensaje
Otra cosa ... Una diferencia fundamental entre un arbol y un graph es que el nodo de un arbol puede tener 1 y solo 1 padre, en este yo no veo 2 padres para un nodo oO
Lo que en realidad estás diciendo, es que la diferencia entre un árbol y un graph, es cómo lo pintas.Pero, mientras el ángulo de las líneas que dibujes no sea parte de la definición del problema, es algo que puedes pintar como quieras.Prueba a pintar ángulos de 90 grados en vez de 180 para el primer hijo, por ejemplo.

La diferencia fundamental entre un árbol y un graph, es que el árbol tiene un *criterio de ordenación*.Y, dado ese criterio, la raíz es una, y sólo puede ser esa.
Los nodos se han añadido según un cierto criterio.Sea porque se use en un algoritmo de ordenación, o sea porque es un arbol tipo "categorias",sea por lo que sea, el nodo raíz tiene un significado semántico que hace que sea el raíz.Por ejemplo, en un árbol de categorías, se cumple que los nodos hijos están semánticamente incluidos en su nodo padre (las categorias hijas pertenecen a la categoría padre).

Cita:
Iniciado por bulter Ver Mensaje
El caso es de 9 o 19 relaciones y no de 100000, asi que tampoco me costo tanto.
Juas

Cita:
Iniciado por bulter Ver Mensaje
Un array del tipo nodo ? eso como se hace?
En la expresión array(<nodo>=><veces que se pasa por el nodo>), tanto una cosa como la otra, significa "representación de".Obviamente, no puedes poner un nodo en un array.Ni tampoco puedes poner las sentencias ejecutadas por el ordenador en la iteración por la que pasó por dicho nodo, que es lo que significa "vez que se pasó por el nodo".
Es muy sencillo.Cuando se pasa por el nodo "4" un numero de veces "2", el array es array("4"=>2).
  #26 (permalink)  
Antiguo 08/06/2013, 16:45
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

Las diferencias entre arbol y graph son:
- En un arbol dos vertices estan conectados tan solo por 1 camino/path
- El arbol no tiene ciclos
- El arbol es conexo
- Seria un arbol si tiene Edges = V-1
es decir: |E| = |V|-1

Cita:
La diferencia fundamental entre un árbol y un graph, es que el árbol tiene un *criterio de ordenación*
what? Que los arboles tienen que ser ordenados ( sorted ) ? oO
Eso no es verdad para nada.

Cita:
En la expresión array(<nodo>=><veces que se pasa por el nodo>), tanto una cosa como la otra, significa "representación de".Obviamente, no puedes poner un nodo en un array.Ni tampoco puedes poner las sentencias ejecutadas por el ordenador en la iteración por la que pasó por dicho nodo, que es lo que significa "vez que se pasó por el nodo".
Es muy sencillo.Cuando se pasa por el nodo "4" un numero de veces "2", el array es array("4"=>2).
A vale vale, te entendí mal respecto a eso.
  #27 (permalink)  
Antiguo 08/06/2013, 17:13
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por bulter Ver Mensaje
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:
... 
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 Ver Mensaje
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.
  #28 (permalink)  
Antiguo 08/06/2013, 17:21
Avatar de bulter  
Fecha de Ingreso: enero-2008
Mensajes: 137
Antigüedad: 11 años, 11 meses
Puntos: 20
Respuesta: Buscar el camino mas largo

A lol bueno si ... pero ese resultado no lo he sacado con el algoritmo .... lo hice a ojo ... el algoritmo es correcto es hacer un DFS que vaya sumando los values de los nodes. Solo no entendi por que dices que un arbol tiene que ser ordenado :/
  #29 (permalink)  
Antiguo 08/06/2013, 17:23
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Cita:
Iniciado por bulter Ver Mensaje
Las diferencias entre arbol y graph son:
- En un arbol dos vertices estan conectados tan solo por 1 camino/path
- El arbol no tiene ciclos
- El arbol es conexo
- Seria un arbol si tiene Edges = V-1
es decir: |E| = |V|-1
A ver.Un arbol es un grafo dirigido. Así que, no puedes hablar de diferencias entre arbol y grafo, sino entre arbol, y otros grafos que no son árboles.
La clave aquí está en la **dirección**.La dirección se la da una cierta semántica de los objetos representados por los nodos de los árboles.
Exactamente, en este caso concreto, qué caracteristica está definiendo la dirección?

Cita:
Iniciado por bulter Ver Mensaje
what? Que los arboles tienen que ser ordenados ( sorted ) ? oO
Eso no es verdad para nada.
No.Tienen que ser dirigidos.Un tipo de dirección podría ser un criterio de ordenación.Menores a la izquierda, mayores a la derecha.Pero eso no convierte al arbol en "ordenado".Una cierta interpretación del arbol daría una lista ordenada de números, pero eso es una interpretación, no el árbol en sí.
En este caso, la semántica de los nodos viene dada por el hecho de que los números son ordenables por "mayor" y "menor", y eso define la dirección.

Por cierto, no me has comentado nada de eso de que el 7 no podía ser el nodo root...Que eso lo convertía en un forest...Tengo curiosidad.
  #30 (permalink)  
Antiguo 08/06/2013, 17:39
Avatar de dashtrash
Colaborador
 
Fecha de Ingreso: abril-2007
Ubicación: Ni en Sevilla,ni en Sanlúcar..qué más da..
Mensajes: 926
Antigüedad: 12 años, 8 meses
Puntos: 269
Respuesta: Buscar el camino mas largo

Vamos a replantear el problema, con el caso anterior, que es exactamente el dado por el OP:
Dados una serie de tramos de carretera, (y para seguir manteniendo las erroneas suposiciones, que son conexas y sin ciclos), encontrar el camino más largo que una a 2 poblaciones cualquiera.

Dime por qué esta estructura de datos es un árbol.Por qué hay un nodo "raiz" en este problema.Y por qué ese nodo "raiz" es el que "NUNCA aparezca en la derecha" de la lista de tramos que nos den.

Etiquetas: arboles, largo, node
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 1 personas




La zona horaria es GMT -6. Ahora son las 08:15.