Cita:
Iniciado por pateketrueke 
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 < 0 || $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
Este tema le ha gustado a 1 personas