PrEDA: grafos, el algoritmo de Kruskal

Otro code-kata que vengo a traer.. Siguiendo con la serie de los relacionados con los grafos, el algoritmo de Kruskal. Es parecido al algoritmo de Prim del post anterior pero con distinto rendimiento según el tipo de grafo que tengamos. Si tenemos un grafo denso es más eficiente el algoritmo de Prim, pero si es un grafo disperso el de Kruskal.

Este algoritmo busca conseguir el árbol de recubrimiento mínimo de un grafo. Es decir, cada arista que une vértices del grafo tiene un coste. Entonces, se busca el árbol de coste mínimo que conecte a todos los nodos. Este algoritmo se puede aplicar para construcción de redes con coste mínimo, por ejemplo: Internet, redes locales, eléctricas, de agua, etc..

Se utiliza la estrategia de programación voraz. Se van eligiendo las siguientes aristas de forma que no hay que volver atrás en la construcción de la solución. Se basa en el concepto de componente conexa y en el ordenamiento previo de las aristas. Vamos a ver..

Los pasos del algoritmo

1. Se ordenan todas las aristas en orden creciente de coste.
2. Se parte de un vector de componentes conexas que inicialmente es 1 componente por nodo.
3. Cada vez que se añade una nueva arista al árbol final, se tienen que unir dos componentes conexas.
4. Se repite el paso 3 hasta que sólo hay 1 componente conexa que contiene todos los nodos o nos hayamos quedado sin aristas.

Un ejemplo

Viéndolo queda claro el funcionamiento. Primero se lista la lista de adyacencia y luego una traza del funcionamiento:

0 --> 4(5) --> 5(1) --> 1(3)
1 --> 8(5) --> 0(3)
2 --> 5(1) --> 11(3)
3 --> 8(2)
4 --> 0(5) --> 11(5) --> 8(4)
5 --> 0(1) --> 2(1) --> 10(5) --> 9(4)
6 --> 8(2) --> 9(5)
7 --> 10(2) --> 11(2)
8 --> 1(5) --> 3(2) --> 4(4) --> 6(2) --> 9(3)
9 --> 5(4) --> 8(3) --> 6(5)
10 --> 5(5) --> 7(2)
11 --> 2(3) --> 4(5) --> 7(2)
0-5(1) {0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}{11} N1=0 N2=5 using this edge!
5-0(1) {0,5}{1}{2}{3}{4}{6}{7}{8}{9}{10}{11} N1=0 N2=0 not using..
5-2(1) {0,5}{1}{2}{3}{4}{6}{7}{8}{9}{10}{11} N1=0 N2=2 using this edge!
2-5(1) {0,5,2}{1}{3}{4}{6}{7}{8}{9}{10}{11} N1=0 N2=0 not using..
8-3(2) {0,5,2}{1}{3}{4}{6}{7}{8}{9}{10}{11} N1=8 N2=3 using this edge!
8-6(2) {0,5,2}{1}{4}{6}{7}{8,3}{9}{10}{11} N1=8 N2=6 using this edge!
11-7(2) {0,5,2}{1}{4}{7}{8,3,6}{9}{10}{11} N1=11 N2=7 using this edge!
3-8(2) {0,5,2}{1}{4}{8,3,6}{9}{10}{11,7} N1=8 N2=8 not using..
10-7(2) {0,5,2}{1}{4}{8,3,6}{9}{10}{11,7} N1=10 N2=11 using this edge!
6-8(2) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=8 N2=8 not using..
7-10(2) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=10 N2=10 not using..
7-11(2) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=10 N2=10 not using..
0-1(3) {0,5,2}{1}{4}{8,3,6}{9}{10,11,7} N1=0 N2=1 using this edge!
1-0(3) {0,5,2,1}{4}{8,3,6}{9}{10,11,7} N1=0 N2=0 not using..
8-9(3) {0,5,2,1}{4}{8,3,6}{9}{10,11,7} N1=8 N2=9 using this edge!
2-11(3) {0,5,2,1}{4}{8,3,6,9}{10,11,7} N1=0 N2=10 using this edge!
11-2(3) {0,5,2,1,10,11,7}{4}{8,3,6,9} N1=0 N2=0 not using..
9-8(3) {0,5,2,1,10,11,7}{4}{8,3,6,9} N1=8 N2=8 not using..
4-8(4) {0,5,2,1,10,11,7}{4}{8,3,6,9} N1=4 N2=8 using this edge!
5-9(4) {0,5,2,1,10,11,7}{4,8,3,6,9} N1=0 N2=4 using this edge!
Final edges: 0-5 5-2 8-3 8-6 11-7 10-7 0-1 8-9 2-11 4-8 5-9

Lo que hay entre llaves {} son las componentes conexas. Lo que hay entre paréntesis () son costes o pesos de las aristas.

El algoritmo

<?php

define('NUMBER_OF_NODES', 12);
define('NUMBER_OF_EDGES_PER_NODE', 2);
define('MAX_COST', 5);

$adjacentList = array();
fillRandomCosts($adjacentList);
printToScreenAdjacentList($adjacentList);

$finalEdges = kruskal($adjacentList);

// Printing solution.
if (count($finalEdges) < NUMBER_OF_NODES - 1) {
    echo 'Not full connected graph!!'.PHP_EOL;
} else {
    echo 'Final edges: ';
    foreach ($finalEdges as $edge) {
        echo $edge['n1'].'-'.$edge['n2'].' ';
    }
    echo PHP_EOL;
}

function kruskal($adjacentList)
{
    $orderedEdges = orderEdgesWithCosts($adjacentList);
    $finalEdges = array();

    // Init each set with each node.
    $sets = array();
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
        $sets[] = array($i);
    }

    // Finding edges.
    while (count($finalEdges) < NUMBER_OF_NODES - 1 and count($orderedEdges) > 0) {
        $nextEdge = array_shift($orderedEdges);

        $componentN1 = searchConnectedComponent($nextEdge['n1'], $sets);
        $componentN2 = searchConnectedComponent($nextEdge['n2'], $sets);

        echo $nextEdge['n1'].'-'.$nextEdge['n2'].'('.$nextEdge['cost'].') ';
        foreach ($sets as $set) {
            echo '{'.implode(',', $set).'}';
        }
        echo ' N1='.$componentN1.' N2='.$componentN2;

        if ($componentN1 != $componentN2) {
            // Fuse component 2 into 1.
            foreach ($sets[$componentN2] as $node) {
                $sets[$componentN1][] = $node;
            }
            unset($sets[$componentN2]);

            // Adds this edge to solution.
            $finalEdges[] = array(
                'n1' => $nextEdge['n1'],
                'n2' => $nextEdge['n2'],
            );

            echo ' using this edge!';
        } else {
            echo ' not using..';
        }

        echo PHP_EOL;
    }

    return $finalEdges;
}

function searchConnectedComponent($node, $sets)
{
    foreach ($sets as $key => $set) {
        if (in_array($node, $set)) {
            return $key;
        }
    }
}

function orderEdgesWithCosts($adjacentList)
{
    $orderedEdges = array();
    for ($i = 1; $i <= MAX_COST; ++$i) { foreach ($adjacentList as $nodeFromNumber => $nodeFromValues) {
            foreach ($nodeFromValues as $nodeToNumber => $nodeToCost) {
                if ($nodeToCost == $i) {
                    $orderedEdges[] = array(
                        'cost' => $nodeToCost,
                        'n1' => $nodeFromNumber,
                        'n2' => $nodeToNumber,
                    );
                }
            }
        }
    }

    return $orderedEdges;
}

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, MAX_COST);
                    $adjacentList[$i][$adjacentNode] = $adjacentNodeCost;
                    $adjacentList[$adjacentNode][$i] = $adjacentNodeCost;
                    $added = true;
                }
            }
        }
    }
}

function printToScreenAdjacentList($adjacentList)
{
    for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { echo $i; foreach ($adjacentList[$i] as $key => $value) {
            echo ' --> '.$key.'('.$value.')';
        }
        echo PHP_EOL;
    }
}