| 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($node, 0);
}
}
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() == 1 && $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 :) |