Algoritmo de Kruskal

Escrito por Rodrigo Burgos Domínguez

Algoritmo de Kruskal Kruskal es una algoritmo muy utilizado en los concursos para la resolución de problemas que tiene que ver con el árbol de expansión mínima( MST) , la técnica de Kruskal, es ordenar todas las aristas ( dependiendo si uno quiere la expansión mínima o máxima) , al ordenar las aristas con el menor costo se va agregando la arista menor formando un árbol, en el momento que al agregar una arista se agregue un ciclo esta arista no es considerada parte de la solucion.

Vamos a elaborar el código paso por paso:

Creamos una estructura de datos llamada Arista:

typedef struct { int a, b, cost; } Arista;

en esta estructura de datos vamos a guardar la información de cada arista, el nodo origen 'a', el nodo destino 'b' y obviamente el costo de la arista 'cost', posteriormente declaramos el arreglo donde vamos a guardar todas nuestras aristas:

# define MAX_ARISTA 100000 // dependiendo el numero de aristas:

Arista[MAX_ARISTA +1] A;  

Bueno eso es solo una parte del problema el como guardar la información ahora veamos el algoritmo:

Supongamos que N es el numero de nodos y M el numero de aristas, tenemos el siguiente seudocódigo ( como aparece en Wikipedia http://en.wikipedia.org/wiki/Kruskal's_algorithm ):

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

Vamos a seguir este algoritmo, la única diferencia que nosotros nada mas vamos a regresar el costo

int kruskal(int N, int M){
  int x, sol = 0, a, b, contAristaAgregadas = 0;
  for( x = 0 ; x <= N; x++) set[x] = x;
  qsort( A, M, sizeof( ARISTA ), compare );
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
      contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);
}

como puedes observar, creamos nuestro conjunto o mejor dicho lo inicializamos:

for( x = 0; x <= N; x++) set[x] = x;

este arreglo lo que quiere decir es que el conjunto 0 pertenece al conjunto 0, el conjunto 1 al conjunto 1, en pocas palabras cada conjunto contiene solo un elemento, el mismo, al inicio todos los nodos perteneces a su correspondiente conjunto, nodo 0 al conjunto 0 , nodo 1 al conjunto 1, etc.

posteriormente se ordenan las aristas:

qsort( A, M, sizeof( ARISTA ), compare );

Esta función es parte de ANSI C , y lo único que se tiene que agregar es la función comparar que seria de la siguiente manera:

int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }

Esta función compara *a y *b, si *a es menor a *b debe regresar un numero negativo, si es mayor un positivo y si es igual debe regresar 0.

Para el caso de c++, también se puede ordenar con la función sort

# include "algorithm"

bool compare(ARISTA a, ARISTA b){ return a.cost < b.cost; }

// ordenacion

sort( A, A + M , compare);

El siguiente paso es iterar todas las aristas, como ya están ordenadas van de menor a mayor:

  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
      contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }

aquí hay algo curioso y esta parte amerita una explicación mas profunda ya que es lo que hace posible el la unión de conjunto el getSet , ¿que es esta función?

Esta función lo que hace es lo siguiente:

int getSet( int conjunto) { 
   if( set[conjunto] == conjunto) return nodo;
   set[conjunto] = getSet( set[conjunto]);
   return set[conjunto];
}

Lo que valida es si el conjunto que esta preguntando pertenece al mismo conjunto del que empezó,esto quiere decir que nadie a movido a ese conjunto, en otro caso si lo han movido y ahora el conjunto pertenece a otro conjunto, en ese momento podemos regresar que pertenece al conjunto guardado pero puede ser que el conjunto al que apunta ahora pertenezca a otro conjunto, entonces recursivamente se mueve al siguiente conjunto getSet( set[conjunto]), y así aseguramos que regresemos realmente el conjunto que pertenece el nodo en cuestión.

Como se observa al regresar el siguiente conjunto actualizamos el valor

   set[conjunto] = getSet( set[conjunto]);

Esto es para que la búsqueda sea optima, si por ejemplo el conjunto 1 apunta al 2, el 2 al 3, el 3, al 4, … y el 9999 al 10000 , se procesaría cada consulta del nodo 1 diez mil veces, pero al agregar esta actualización la siguiente vez que se pregunte sobre el nodo 1, solo se consultaría el conjunto 1 y el 10000 y validaría si el 10000 no ha sido modificado.

Esta parte es crucial en el algoritmo y deben entender bien la función getSet.

siguiendo con el algoritmo de Kruskal:

  // RECORDANDO 
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
      contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  

lo que sigue es validar que el conjunto de la arista de ‘a’ sea diferente de la arista de ‘b’ , por tanto se realiza por medio de esto:

     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
     }

si a ¡= b entonces no perteneces al mismo conjunto y se agrega la arista como parte de la solución:

       contAristaAgregadas++;
       set[a] = b;
       sol += A[x].cost; 

en conAristasAgregadas, el nombre lo dice todo , contamos el numero de aristas agregadas, hacemos el conjunto ‘a’ que pertenesca al conjunto de 'b':

set[a] = b;  // si, así de fácil.

y sumamos la arista:

sol += A[x].cost; 

al final del algoritmo debemos garantizar que sea conexo, y para eso validamos el numeró de aristas agregadas sean igual al N – 1 :

  return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);

si es igual a N – 1, regresamos la solución que llevamos, en otro caso regresamos infinito en este caso 2 a la 28 ( este valor puede no ser suficiente si el costo de las aristas es muy grade, hay que tener cuidado en esto).

al final nuestro algoritmo queda de la siguiente manera:

# include "stdio.h"
# include "string.h>
# define MAX_ARISTAS 5000000
# define MAX_NODES 2000

int set[MAX_NODES + 1];

int getSet( int conjunto ){ 
  return set[ conjunto ] == conjunto ? conjunto : (set[conjunto] = getSet( set[conjunto] ) );
}

typedef struct { int a, b, cost; } ARISTA;

ARISTA A[MAX_ARISTAS + 1];


int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }

int kruskal(int N, int M){
  int x, sol = 0, a, b, contAristaAgregadas  = 0;
  for( x = 0 ; x <= N; x++) set[x] = x;
  qsort( A, M, sizeof( ARISTA ), compare );
  for( x = 0; x < M; x++){
     a = getSet( A[x].a);
     b = getSet( A[x].b);
     if( a != b){
       contAristaAgregadas ++;
       set[a] = b;
       sol += A[x].cost; 
     }
  }
  return ( contAristaAgregadas  == N - 1 ) ? sol : (1<<28);
}

Un ejemplo de kruskal es este 2533 - Connecting Cities



Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com