Buscar el camino mas largo

[bulter]

aaaa lo arboles no tienen que ser dirigidos

Iniciado por Wikipedia

more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without simple cycles is a tree

http://en.wikipedia.org/wiki/Tree_(graph_theory)

Menores a la izquierda, mayores a la derecha....
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.

Aqui estas ablando de Binary tree que es otro tema oO entonces si que tienen que ser ordenados. Numeros menores a izquierda y menores a derecha y cada nodo puede tener 2 hijos como mucho... pero eso es Binary Tree, y no estamos hablando de el...

Lo del nodo 7. la verdad es que ni me entere de como lo hiciste root, tirando lo hacia arriba ... si lo tiras hacia arriba cambias todas las conexiones y todo el arbol asi que aqui a lo mejor no te entendi yo bien por eso no lo mencione.

Por cierto aqui tienes el codigo, que elimina las direcciones de espejismo:

Código PHP:

  <?php

class NodePaths
{
    private $VisitedNodes = array();
    private $MaxSum = 0;
    private $nodeList = array();
    private $longestPath = "";
    private $foundedPaths = array();
    
    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($node, 0);
                echo "<br />";
            }
        }
        
        return array("MaxSum" => $this->MaxSum, "MaxPath" => $this->longestPath);
    }
    
    private function LongestPathDFS(Node $node, $currentSum, array $path = array())
    {
        $this->VisitedNodes[] = $node->value;
        $currentSum += $node->value;
        $path[] = $node->value;
        
        if($node->NumberOfChildren() == 1)
        {
            // skip mirror effect
            if(!in_array(implode(",", array_reverse($path)), $this->foundedPaths) && 
               !in_array(implode(",", $path), $this->foundedPaths) && 
               count($path) > 1)
            {
                $this->foundedPaths[] = implode(",", $path);
                echo "[". implode("," ,$path) . "]";
            }
        }
        
        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() == 1 && $currentSum > $this->MaxSum)
        {
            $this->MaxSum = $currentSum;
            $this->longestPath = implode(",", $path);
        }
    }
}


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

echo "Max Path: " . $pathResult["MaxPath"] . "(" . $pathResult["MaxSum"] . ")<br />";
?>   

Resultado:

Código:

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

Max Path: 7,8,1,5,11,2,15(49)

[bulter]

No me acorde antes de mirar en wikipedia :|

A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:
G is connected and has no cycles.
G has no cycles, and a simple cycle is formed if any edge is added to G.
G is connected, but is not connected if any single edge is removed from G.
G is connected and the 3-vertex complete graph is not a minor of G.
Any two vertices in G can be connected by a unique simple path.
If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:
G is connected and has n − 1 edges.
G has no simple cycles and has n − 1 edges.

Prácticamente lo que dije con 2-3 cositas mas..

A tree is an undirected simple graph,
G has no cycles,
Any two vertices in G can be connected by a unique simple path.
G has no simple cycles and has n − 1 edges.

Y lo que tu me estas diciendo de Binary tree ( que es un TIPO de arbol ) es correcto pero no lo mismo:

In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. A tree which does not have any node other than root node is called a null tree. In a binary tree, a degree of every node is maximum two. A tree with n nodes has exactly n−1 branches or degree.

[dashtrash]

Claro..Lo que tienes ahi, es un tree como tipo de grafo.Si un grafo cumple eso, le llamas un tree...Lo que pasa es que ese tree, es el concepto MATEMATICO, no es el "tree" que tú instintivamente estás pensando.Ése es el rooted tree (lee un poco más abajo).

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. ---
Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science;

Yo diría que todo lo que has pintado, es un "rooted tree".Así que, para pintar los árboles que has estado usando, vas a tener que:
1) Designar un root : aún no me has dado ninguna razón de por qué has hecho la elección del root.Ni siquiera de por qué existe.
2) De dónde sale la "orientación natural" (orientación=>dirección , natural=>semántica (naturaleza) de los datos).

Vamos, que estamos donde antes.Los árboles que has estado pintando, son rooted trees, que deberían tener un criterio por el cual el root es el root, y una forma de definir la orientación, o dirección de los nodos.

Y, es la segunda vez que lo digo : El ejemplo del binary tree, no es para decir que todo arbol es, ni binario, ni ordenado numéricamente.Es para decir que hay un criterio de orientación,dirección,ordenación, como quieras.Un criterio definido que indica por qué un nodo es el raíz, y por qué un nodo es hijo de otro, y no al revés.
A ver, supón un árbol de 2 nodos.Simplemente, 1 segmento, que une A y B.Eso también es un grafo, y un árbol (matemático), pero NO tiene raíz hasta que me digas un criterio que diga que la raíz es A o B.Lo puedes pintar con A arriba, o abajo de B.A puede ser hijo de B, o al revés.
Y eso no convierte a ninguno en raíz hasta que no especifiques el criterio....A ver si esta vez ya pillas la idea..

Que da igual.Un binary tree.Un árbol de categorías, un árbol de tareas-subtareas..Lo que quieras...Hay un criterio que dice A) quien es el root, B) por qué un nodo es hijo del otro.Por qué hay una dependencia: por orden, por contenimiento, o por cualquier otro motivo.

[bulter]

.Simplemente, 1 segmento, que une A y B.Eso también es un grafo, y un árbol (matemático), pero NO tiene raíz

Con esto esoy de acuerdo.
Vamos por partes por que se nos monta 1 lio. Primero vamos por la raiz.
Por que el 1 ? Es el unico elemento que no tiene padre. Yo no veo otro que no tenga padre... Si vez a otro se que me equivoco yo. Y estamos hablando de tree no de forest.

[dashtrash]

Pero bueno, aparte, esto ya me da igual.Mi intención es simplemente advertir al OP que la larga parrafada sobre árboles no viene al caso, que parte de supuestos incorrectos, y, aún bajo sus supuestos, sigue siendo incorrecta (criterio de selección de root incorrecto).
Con un array de arrays de segmentos, y una lista de segmentos visitados, es posible resolver el problema original.Incluidos grafos con ciclos, e inconexos.
La analogía del camino más largo que une a 2 ciudades cualquiera, sirve para entender mejor el problema.

[bulter]

Bueno dejemos lo de lo supuestos, que tu ves un arbol/graph yo otro :/
Y el algoritmo no es 1 unico pueden ser varios. Teniendo un arbol tal y como lo tengo en el dibujo como buscarias tu la ruta mas larga ?

[dashtrash]

Iniciado por bulter

Por que el 1 ? Es el unico elemento que no tiene padre. Yo no veo otro que no tenga padre... Si vez a otro se que me equivoco yo. Y estamos hablando de tree no de forest.

Quien dice que, para el 1, el 7 es un hijo, y no su padre?
Es una idea instintiva que viene de la forma en la que lo has dibujado.No hay nada del problema que lo diga.No has violado ninguna regla del problema.No hay dirección,no hay orientacion así que puedes ir del 1 al 7, o del 7 al 1.Puedes ir de A a B, o de B a A.

Te lo digo de nuevo.
Mueve el 7 hacia arriba, hasta que esté por encima del 1.
Ahora el 7 es el root.
Pero, después, mueve el 8 o el 9 hacia arriba.Cualquiera.Vaya, se convierte en el root.El que hayas escogido, ha pasado de ser una hoja, a ser el root.
O hay un criterio de dirección, y que impida que el 1 sea hijo del 7, o no existe un root.Mejor dicho.Root es cualquier nodo.

[dashtrash]

Iniciado por bulter

Bueno dejemos lo de lo supuestos, que tu ves un arbol/graph yo otro :/
Y el algoritmo no es 1 unico pueden ser varios. Teniendo un arbol tal y como lo tengo en el dibujo como buscarias tu la ruta mas larga ?

No es necesario hacer un bucle de recursiones.Con una recursión es bastante.
La "ley" del problema sería que los extremos del camino más largo, van a ser 2 hojas.
El matiz que hay que tener en cuenta , es que dado un nodo que no sea una hoja,
debajo de él pueden estar, 0, 1 o 2 de los extremos del camino más largo.
Así que en cada llamada recursiva, no es bastante con devolver el camino a la hoja más alejada, sino el camino más largo que una a dos hojas bajo ese nodo.

Generalizando, al llegar al root, se tendrá el camino más largo que una a dos hojas bajo ese nodo, que es el camino más largo total.

[XpoZed]

Gracias chicos. Ya lo tengo claro mas o menos.

Dash bulter esta en lo correcto, yo me explique mal por lo cual lo siento



Aqui esta lo que habia que hacer:

We are given a tree of N nodes, each containing a distinct integer number (between 1 and 2147483640,
inclusive) and optionally a set of descendent nodes. Write a program that finds a path from some leaf of
the tree to another (different) leaf of the tree with maximal sum of its nodes and prints this sum.
Input
The input data should be read from the console.
The first input line contains N - the number of nodes in the tree.
At the next N-1 lines there are pairs of numbers in format (p1 <- p2) each meaning that node p1 is
parent of the node p2. See the example bellow.
The input data will always be valid and in the described format. There is no need to check it explicitly.
Output
The output data should be printed on the console.
At the only output line you should print the maximal sum of nodes found.
Constraints
 N will be between 2 and 3000, inclusive.
 Allowed working time for your program: 0.80 seconds.
 Allowed memory: 16 MB

Y la solucion dada ( bueno es en C# )

Código C#:

private static int FindLongestPath(Node<int> root)
        {
            if (root.Children.Count == 0)
            {
                return 0;
            }
 
            int maxPath = 0;
            foreach (var node in root.Children)
            {
                maxPath = Math.Max(maxPath, FindLongestPath(node));
            }
 
            return maxPath + 1;
        }
 
private static List<Node<int>> FindAllLeafs(Node<int>[] nodes)
        {
            List<Node<int>> leafs = new List<Node<int>>();
 
            foreach (var node in nodes)
            {
                if (node.Children.Count == 0)
                {
                    leafs.Add(node);
                }
            }
 
            return leafs;
        }
 
static void Main(string[] args)
        {
 var N = int.Parse(Console.ReadLine());
            var nodes = new Node<int>[N];
 
            for (int i = 0; i < N; i++)
            {
                nodes[i] = new Node<int>(i);
            }
 
            for (int i = 1; i <= N - 1; i++)
            {
                string edgeAsString = Console.ReadLine();
                var edgeParts = edgeAsString.Split(' ');
 
                int parentId = int.Parse(edgeParts[0]);
                int childId = int.Parse(edgeParts[1]);
 
                nodes[parentId].Children.Add(nodes[childId]);
                nodes[childId].HasParent = true;
            }
....
}
 

Que prácticamente es lo que dijo bulter pero en C#, siento no haber me explicado mejor
Saludos

[dashtrash]

Eso no es tener "razón", ya que no había nada en el planteamiento inicial, que "razonablemente" llevara a suponer que los datos iniciales formaran un árbol. Bulter hizo una presuposición que casualmente coincide con el problema que ves.

Ese código que pegas en C#, no devuelve la distancia máxima entre dos hojas, basada en el peso de los nodos.Devuelve la profundidad máxima del árbol (la mayor distancia en nodos del root, a una de sus hojas), independientemente del peso.

Ni devuelve el coste (suma del valor de los nodos), ni el path (nodos recorridos).La función recursiva sólo usa de cada nodo, la propiedad Children, y Children.Count. En ninún lado usa el "id" que pasa en el constructor de los nodos, que se supone que es el peso.En ningún lado hay una suma.

Mira la función recursiva "FindLongestPath".
Ahora, imaginate que estás en el nodo "8" de tu ejemplo.
La función FindLongestPath, para el nodo "8", devuelve 1.
El valor 1, ni es el peso de los nodos (debería ser 7 o 15, dependiendo de la estrategia), ni el camino (array(7) o array(7,8) , dependiendo de la estrategia).

[XpoZed]

dashtrash como quieres mover el 7 hacia arriba ? entonces se quedaria que el 7 tiene conexion con el 1:

7-1
1-8

entonces cambia todo, y yo no he dicho que el 7 esta directamente conectado con el 1, no puedes cambiar las conexiones que di, para demonstrar que tienes razon, el 1 esta conectado con el 7 pero mediante el 8, eso de que tu lo cambias y sigue habiendo conexion no lo hace correcto

[dashtrash]

Esto ya empieza a ser demasiado...A ver, que da igual, que en un dibujo de bulter habia una conexion entre el 1 y el 7..Amos a ver si ya empezamos a pensar un poquito y dejarnos de dibujitos..En el que acabas de poner tú,dime por qué el 1 es padre del 8, y no al revés.
Por qué el 8 es padre del 7, y no hijo del 7..Mueve el 5 como hijo del 11, y se convierte el 11 en el root...Que no hay root..Que no hay criterio de ordenación...Y que todo esto ya se ha dicho..

[bulter]

Xpozed, dashtrash se refiere que di por casualidad que numero es el padre y cual el hijo por que te faltan las direcciones:

5-11,
1-8,
11-3,
8-7,
1-5,
11-2,
8-6,
2-15,
8-4

es decir, que los padres podrian ser los numeros de la derecha y no de la izquierda, tenian que haber sido:

5<-11,
1<-8,
11<-3,
8<-7,
1<-5,
11<-2,
8<-6,
2<-15,
8<-4

Por que si hubiera asumido que los padres son los de la derecha obtendria una cosa que es totalmente distinta. Seria algo asi:



Entonces 7,6,4,3,15 seran roots , 1 tendria 2 padres igual que 11 , 8 tendria 3 , haria solo 1 hoja ( el 1 ) y esto seria otra cosa
Aun que el resultado de las rutas seria el mismo no seria de From leaf to leaf, si no, From root to root

[dashtrash]

Iniciado por bulter

Aun que el resultado de las rutas seria el mismo no seria de From leaf to leaf, si no, From root to root

Nada..Que no consigo explicarme..No sería from root to root..Sigue siendo de hoja a hoja, o , en realidad, como quieras llamarlo...Porque no hay nada que defina a los nodos como raíces o como hojas..cómo lo explico...
Tú dices que es de "root a root" por cómo lo has pintado...Si lo pintaras asi:

Sigue siendo de "root a root"? Porque es el mismo árbol que has pintado tú, pero, como "visualmente" he colocado en otro ángulo las uniones, ahora...sería de leaf a leaf? De leaf a root? De root a root?
Mientras no haya criterio de ordenación, no hay ni leafs, ni roots.Y esto es , en estructura de datos, un árbol, como podría ser cualquier otra cosa (array de arrays).