Hoy vuelvo a traer otro code-kata, siguiendo con la serie de algoritmos de programación relacionados con los grafos. Esta vez se trata del algoritmo de Prim, que sirve para calcular el árbol de recubrimiento de mínimo coste de un grafo.
Es decir, tenemos un grafo que se compone de nodos, que se interconectan mediante aristas. Dichas conexiones entre nodo y nodo, tienen un coste. Entonces queremos hallar la forma de interconectar todo con el mínimo coste. Una aplicación directa de esto puede ser para una red de ordenadores, eléctrica, tuberías, carreteras, etcétera.. mediante este algoritmo puedes obtener la forma de mantener conectados todos los nodos del grafo con el mínimo coste.
Este algoritmo usa la estrategia de programación voraz. Mediante ésta se elige una forma de ir creando la solución sin rectificar volviendo atrás.
Pasos del algoritmo de Prim
Se divide en los siguientes:
- Se crean dos vectores, uno con los nodos que ya están en el árbol de recubrimiento mínimo (vector usados), y los que no (vector no usados).
- Se elige arbitrariamente el nodo raíz, se pone en el vector de los nodos del árbol usados. El resto de nodos en el vector de no usados.
- Se elige el siguiente nodo, de los no usados, que se conecta con alguno de los nodos usados. Pero tiene que ser el que se una a los usados con mínimo coste de la arista. Este nodo elegido se mueve del vector de los no usados al de los usados.
- Así sucesivamente se repite el paso 3 hasta que todos los nodos están en el vector de usados.
El paso principal es el 3, que es el que aplica la estrategia voraz.
Código
<?php
define('NUMBER_OF_NODES', 20);
define('NUMBER_OF_EDGES_PER_NODE', 2);
$adjacentList = array();
fillRandomCosts($adjacentList);
printToScreen($adjacentList);
prim($adjacentList);
function prim($adjacentList)
{
$nodesInTree = array(0);
$nodesNotInTree = array();
for ($i = 1; $i < NUMBER_OF_NODES; ++$i) { $nodesNotInTree[] = $i; } while (count($nodesNotInTree) > 0) {
$nextNodeToAdd = getNextEdge($adjacentList, $nodesInTree, $nodesNotInTree);
$nodesInTree[] = $nextNodeToAdd;
unset($nodesNotInTree[array_search($nextNodeToAdd, $nodesNotInTree)]);
}
}
function getNextEdge($adjacentList, $nodesInTree, $nodesNotInTree)
{
$minCost = 100;
$nextNode = null;
$edge = '';
foreach ($nodesInTree as $node) {
foreach ($adjacentList[$node] as $key => $value) {
if (in_array($key, $nodesNotInTree)) {
if ($value < $minCost) {
$nextNode = $key;
$minCost = $value;
$edge = $node.'-'.$key;
}
}
}
}
echo 'IN '.implode(',', $nodesInTree)
.' NOT IN '.implode(',', $nodesNotInTree)
.' NEXT EDGE TO ADD '.$edge.'('.$minCost.')'.PHP_EOL;
return $nextNode;
}
function fillRandomCosts(&$adjacentList)
{
for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
$added = false;
while (!$added) {
for ($j = 0; $j < NUMBER_OF_EDGES_PER_NODE; ++$j) {
$adjacentNode = rand(0, NUMBER_OF_NODES - 1);
if ($adjacentNode != $i and $adjacentNode != $j) {
$adjacentNodeCost = rand(1, 5);
$adjacentList[$i][$adjacentNode] = $adjacentNodeCost;
$adjacentList[$adjacentNode][$i] = $adjacentNodeCost;
$added = true;
}
}
}
}
}
function printToScreen($adjacentList)
{
for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { echo $i; foreach ($adjacentList[$i] as $key => $value) {
echo ' --> '.$key.'('.$value.')';
}
echo PHP_EOL;
}
}
Marco en negrita lo principal del algoritmo que lo hace voraz, el modo de elegir el siguiente nodo que añadimos al árbol de recubrimiendo mínimo. En la variable $edge es donde vamos poniendo las siguientes aristas. En éste código simplemente se imprimen para ver cómo funciona el algoritmo y comprenderlo.
Un ejemplo
0 --> 7(4) --> 3(4) 1 --> 7(3) --> 6(3) 2 --> 14(2) --> 6(5) 3 --> 0(4) --> 9(5) --> 12(1) --> 18(1) 4 --> 8(2) --> 15(1) --> 17(5) --> 19(1) 5 --> 19(5) --> 13(4) 6 --> 2(5) --> 1(3) --> 9(5) --> 16(3) 7 --> 0(4) --> 1(3) --> 12(2) --> 16(2) --> 8(2) --> 10(2) 8 --> 4(2) --> 7(2) --> 19(2) 9 --> 3(5) --> 6(5) --> 18(1) --> 16(5) 10 --> 19(1) --> 7(2) --> 15(3) 11 --> 12(5) --> 16(3) 12 --> 7(2) --> 11(5) --> 18(4) --> 3(1) 13 --> 5(4) --> 18(3) 14 --> 2(2) --> 19(5) 15 --> 4(1) --> 10(3) 16 --> 7(2) --> 9(5) --> 11(3) --> 6(3) 17 --> 4(5) 18 --> 9(1) --> 12(4) --> 13(3) --> 3(1) --> 19(5) 19 --> 5(5) --> 8(2) --> 10(1) --> 14(5) --> 18(5) --> 4(1) IN 0 NOT IN 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 NEXT EDGE TO ADD 0-7(4) IN 0,7 NOT IN 1,2,3,4,5,6,8,9,10,11,12,13,14,15,16,17,18,19 NEXT EDGE TO ADD 7-12(2) IN 0,7,12 NOT IN 1,2,3,4,5,6,8,9,10,11,13,14,15,16,17,18,19 NEXT EDGE TO ADD 12-3(1) IN 0,7,12,3 NOT IN 1,2,4,5,6,8,9,10,11,13,14,15,16,17,18,19 NEXT EDGE TO ADD 3-18(1) IN 0,7,12,3,18 NOT IN 1,2,4,5,6,8,9,10,11,13,14,15,16,17,19 NEXT EDGE TO ADD 18-9(1) IN 0,7,12,3,18,9 NOT IN 1,2,4,5,6,8,10,11,13,14,15,16,17,19 NEXT EDGE TO ADD 7-16(2) IN 0,7,12,3,18,9,16 NOT IN 1,2,4,5,6,8,10,11,13,14,15,17,19 NEXT EDGE TO ADD 7-8(2) IN 0,7,12,3,18,9,16,8 NOT IN 1,2,4,5,6,10,11,13,14,15,17,19 NEXT EDGE TO ADD 7-10(2) IN 0,7,12,3,18,9,16,8,10 NOT IN 1,2,4,5,6,11,13,14,15,17,19 NEXT EDGE TO ADD 10-19(1) IN 0,7,12,3,18,9,16,8,10,19 NOT IN 1,2,4,5,6,11,13,14,15,17 NEXT EDGE TO ADD 19-4(1) IN 0,7,12,3,18,9,16,8,10,19,4 NOT IN 1,2,5,6,11,13,14,15,17 NEXT EDGE TO ADD 4-15(1) IN 0,7,12,3,18,9,16,8,10,19,4,15 NOT IN 1,2,5,6,11,13,14,17 NEXT EDGE TO ADD 7-1(3) IN 0,7,12,3,18,9,16,8,10,19,4,15,1 NOT IN 2,5,6,11,13,14,17 NEXT EDGE TO ADD 18-13(3) IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13 NOT IN 2,5,6,11,14,17 NEXT EDGE TO ADD 16-11(3) IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11 NOT IN 2,5,6,14,17 NEXT EDGE TO ADD 16-6(3) IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6 NOT IN 2,5,14,17 NEXT EDGE TO ADD 13-5(4) IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6,5 NOT IN 2,14,17 NEXT EDGE TO ADD 19-14(5) IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6,5,14 NOT IN 2,17 NEXT EDGE TO ADD 14-2(2) IN 0,7,12,3,18,9,16,8,10,19,4,15,1,13,11,6,5,14,2 NOT IN 17 NEXT EDGE TO ADD 4-17(5)
Como tenemos 20 nodos, para tenerlos todos conectados nos salen 19 aristas.
