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)