INGENIERIA EN SISTEMAS COMPUTACIONALES
MODULO
MATEMATICAS DISCRETAS
ARBOL DE EXPANSIÓN.
(DISJOINT-SET-UNION-FIND).
ARBOL BINARIO COMPLETO.
Profesor: Dr. Ulises Barradas Arenas
Lic. en Informática.
Alumno: Jorge Luis Ramírez Ayala.
Ciudad del Carmen Campeche 27 Enero 2019.
1 de 26
Contenido
ARBOL DE EXPANSIÓN MINIMA. 4
ALGORITMO DE KRUSKAL. 5
SU IMPLEMENTACIÓN. 5
BOSQUES DE CONJUNTOS DISJUNTOS. 5
MÉTODO MAKESET. 6
MÉTODO FIND – FIND (X). 6
MÉTODO UNION – UNION ( X , Y ) 10
MEJORAS 14
IMPLEMENTACIÓN DE FIND POR COMPRESIÓN DE CAMINOS 14
IMPLEMENTACIÓN DE UNIÓN POR RANGO 17
VEÁMOSLO AHORA CON EJEMPLO ANTES VISTO 18
EN EL MÉTODO UNIÓN: 18
UNIÓN NORMAL. 21
UNIÓN POR RANGO. 22
NÚMERO DE COMPONENTES CONEXAS 23
CANTIDAD DE VÉRTICES POR COMPONENTE CONEXA. 25
PROBLEMAS DE DIFERENTES JUECES. 26
Bibliografía 1 de 2 26
COMO TRABAJA: 27
ALGORITMO EN PSEUDOCÓDIGO. 27
EL PESO TOTAL DEL ÁRBOL DE EXPANSIÓN MÍNIMA PARA EL GRAFO MOSTRADO
ES 39. 37
VERIFICACIÓN DE MST. 38
Bibliografía 2 de 2 40
2 de 26
ARBOL DE EXPANSIÓN MINIMA:
LLAMADO TAMBIEN ARBOL DE
KRUSKAL.
Antes de empezar con el tema, quiero decirle que se llama también algoritmo
de Kruskal y deberé de comenzar con algunos conceptos sobre lo que es un
árbol de expansión mínima para entender mejor de lo que estamos hablando.
Dados los grafos conexos, no dirigido G, Un árbol de expansión, suele ser un
árbol compuesto por todos los vértices y algunas (posiblemente la mayoría) de
estas aristas G. Al ser creados los arboles no existirán los ciclos, además
deben de existir una ruta entre cada par de vértices.
Un grafo puede llegar a tener muchos árboles de expansión, veamos este
ejemplo:
Arista Arista
Árbol de expansión s s Árbol de expansión
3 de 26
En la imagen podemos apreciar que al observar el grafo arriba, este posee 3
árboles de expansión, dicho esto, los arboles cumplen con propiedades como
son; unir los vértices utilizando simplemente las aristas.
ARBOL DE EXPANSIÓN MINIMA.
Dado el grafo conexo, no dirigido y con pesos en las aristas, un árbol de
expansión mínima es llamado un árbol de expansión compuesto por todos y cada
uno de los vértices y dada cuya suma de sus aristas es la de menor de sus
pesos. Al ejemplo anterior le agregamos pesos en cada arista y obtenemos
como resultado los arboles de expansión siguiente:
Árbol de expansión Arista Arista Árbol de expansión
s s
De esta imagen podemos observar que en el árbol de expansión mínima seria el
primer árbol de expansión cuyo peso total seria de 6, el segundo 9 y por ultimo
8.
Uno de los problemas de hallar el árbol de expansión mínima, puede llegar a ser
resuelto con varios algoritmos, los más conocidos con Prim y Kruskal es que
ambos usan técnicas voraces, llamado (greedy).
4 de 26
ALGORITMO DE KRUSKAL.
Para poder llegar a comprender el algoritmo de Kruskal, sería necesario revisar
primero este tutorial de Unión de Find. (pág. 26) Continúa…
La Unión de Find, es la estructura de Datos que modela una colección de
conjuntos disjuntos (disjoint-sets) y este se basa en dos operaciones.
A. (Find). Determina cual conjunto pertenece al elemento A. Dicha
operación puede ser usada para determinar si 2 de los elementos están o
no en un mismo conjunto.
B. (Unión A / B). Une todos los conjuntos al que pertenecen en A con todo
el conjunto al que pertenece B, dando como resultado a un nuevo
conjunto basado en los elementos tanto de A como dé B.
Dichas operaciones me van a servir para la implementación del algoritmo de
Kruskal o en los problemas que involucran un particionamiento como encontrar
las componentes conexas en un grafo.
SU IMPLEMENTACIÓN.
Explicaremos dos de las formas para implementar Unión - Find en la forma
básica y en las mejoras. Estas al Final encontraran los en C++ y en Java:
BOSQUES DE CONJUNTOS DISJUNTOS.
En esta Implementación representamos a los conjuntos como un árbol, de
donde cada nodo mantiene la información de su nodo padre, y la raíz del árbol
será el elemento representativo de todo el conjunto. Por lo tanto basta con
declarar un arreglo que contenga los elementos del padre de un determinado
elemento:
1 #define MAX 10005
2 int parent[ MAX ]; //Este arreglo contiene el padre del i-esimo nodo
5 de 26
MÉTODO MAKESET.
Para este tipo de Implementación agregamos un método que me inicializara los
conjuntos, el cual llamaremos, MakeSet:
1 //Método de inicialización
2 void MakeSet( int n ){
3 for( int i = 0 ; i < n ; ++i ){
4 padre[ i ] = i; //Inicialmente el padre de cada vértice es el mismo vértice
5 }
6 }
Teniendo como ejemplo 9 vértices, inicializamos por medio de MakeSet:
Ya una vez inicializada podemos unir dos componentes conexas o preguntar con
el método Find si hay un determinado vértice que pertenece a la misma
componente conexa de otro vértice.
MÉTODO FIND – FIND (X).
Como se explica al inicio de este método determina a cual componente conexa
pertenece un vértice X determinado, ello lo hace retornando el vértice raíz del
árbol en el que se encuentra el vértice X.
Por ejemplo:
Teniendo las siguientes componentes conexas vistas como arboles:
6 de 26
Deseo saber la raíz de la componente conexa a la que pertenece el vértice 3:
Al hacer Find ( 3 ) partimos del vértice 3 y subimos hasta la raíz viendo su
padre, en este caso el padre[ 3 ] = 1 por lo tanto:
7 de 26
El vértice actual ahora es el vértice 1 y hacemos lo mismo que antes, padre [ 1 ]
= 0.
Ahora estamos en vértice 0, como el padre [ 0 ] = 0 entonces estamos en la
raíz y la retornamos.
Veamos otro ejemplo, en este caso deseo saber la raíz para el vértice 6:
El vértice actual es 6 vemos su padre [6] = 4 y continuamos:
El vértice actual es 4, padre [4] = 5, todavía posee un padre por lo tanto
continuamos:
8 de 26
El vértice actual es 5 en este caso padre [ 5 ] = 5 hemos llegado a la raíz y la
retornamos.
Por la parte de código la implementación se realizara de manera recursiva,
teniendo como caso base:
1 if( x == padre[ x ] ){ //Si estoy en la raiz
2 return x; //Retorno la raiz
3 }
Si no estoy en la raíz continúo subiendo hasta encontrar la raíz y retornarla:
1 else return Find( padre[ x ] ); //De otro modo busco el padre del nodo
actual, hasta llegar a la raiz.
El código completo:
1 //Método para encontrar la raiz del vértice actual X
2 int Find( int x ){
if( x == padre[ x ] ){ //Si estoy en la raiz
3
return x; //Retorno la raiz
4 }
5 else return Find( padre[ x ] ); //De otro modo busco el padre del vértice
6 actual, hasta llegar a la raiz.
7 }
Del ejemplo anterior podemos agregar un método que me permita saber si dos
vértices están o no en la misma componente conexa, veamos:
9 de 26
En este caso no están en la misma componente conexa. Para saber si están en la
misma componente conexa pues es simplemente ver si poseen la misma raíz, por
lo tanto en código tendríamos:
1 //Método que me determina si 2 vértices estan o no en la misma componente
conexa
2
bool sameComponent( int x , int y ){
3 if( Find( x ) == Find( y ) ) return true; //si poseen la misma raíz
4 return false;
5 }
MÉTODO UNION – UNION ( X , Y )
Como se explicó al inicio este método me permite unir 2 componentes conexas,
ello se realiza por lo siguiente:
A. Obtenemos la raíz del vértice x.
B. Obtenemos la raíz del vértice y.
C. Actualizamos el padre de alguna de las raíces, asignándole como nuevo
padre la otra raíz.
Por ejemplo:
10 de 26
Como se pudo observar primero realizamos los pasos 1 y 2 para hallar las raíces
de ambos vértices y finalmente el paso 3 para actualizar el padre de una de las
componentes conexas, en este caso se actualizará el padre de la componente
conexa X. Continuemos:
Al igual que el caso anterior el nuevo padre del vértice 7 es el vértice 0.
11 de 26
En este caso hemos realizado Unión ( 3 , 1 ), entonces el nuevo padre del
vértice 3 es el vértice 1. Hasta el momento tenemos 6 componentes conexas.
En este caso estamos uniendo dos componentes con más vértices y como se
puede observar solo es necesario actualizar el puntero de la raíz de una de las
componentes.
12 de 26
En la imagen anterior se hizo Union( 6 , 4 ) -> Union( 8 , 4 ) -> Union( 4 , 5 ) en
ese orden.
En esta última imagen hemos unido todos los nodos obteniendo una componente
conexa.
13 de 26
En código tendríamos:
1//Método para unir 2 componentes conexas
2 void Union( int x , int y ){
3 int xRoot = Find( x ); //Obtengo la raiz de la componente del
vértice X
4 int yRoot = Find( y ); //Obtengo la raiz de la componente del vértice
Y
5 padre[ xRoot ] = yRoot; //Mezclo ambos arboles o conjuntos,
6 actualizando su padre de alguno de ellos como la raiz de otro
}
Como pudimos observar cada vez que hagamos unión entre componentes con
mayor número de nodos el árbol tiende a ser un árbol desbalanceado.
MEJORAS
IMPLEMENTACIÓN DE FIND POR COMPRESIÓN DE CAMINOS
La idea de esta mejora es que cada nodo que visitemos en el camino al nodo raíz
puede ser conectado directamente hacia la raíz, es decir al terminar de usar el
método Find todos los nodos que visite tendrán como padre la raíz
directamente. Veamos la mejora en el primer ejemplo del método Find antes
visto:
Al aplicar Find ( 3 ) estamos en vértice 0, como el padre[ 0 ] = 0 entonces
estamos en la raíz y la retornamos.
Compresión de Caminos: Al momento de retornar la raíz en la recursión
actualizamos el padre de cada vértice visitado como la raíz encontrada.
14 de 26
Veamos el otro ejemplo, donde realizamos Find (6):
Realizamos la compresión de caminos, obteniendo:
Veamos ahora de la siguiente imagen realizo Find (3):
15 de 26
Aplicamos compresión de caminos obteniendo:
Como hemos podido observar esta mejora me servirá a futuro ya que si deseo
saber ahora el Find( 3 ) no es necesario recorrer varias veces el padre del
vértice 3 puesto que por la compresión de caminos el vértice 3 está conectado
directamente a la raíz.
Para la implementación basta con una pequeña modificación en el método Find y
es la de modificar lo siguiente:
1//else return Find( padre[ x ] ); //De otro modo busco el padre del
vértice actual, hasta llegar a la raiz.
2 else return padre[ x ] = Find( padre[ x ] ); //Compresion de caminos
Lo que hacemos es cambiar el puntero actual al padre de un nodo en el
recorrido, apuntando a la raíz directamente. Con ello mejoramos la eficiencia
16 de 26
por el hecho de que en futuras llamadas de alguno de los nodos vistos ya no
tendremos que realizar todo el recorrido hacia la raíz simplemente revisara el
padre actual del nodo que es la raíz.
Todo el método:
1//Método para encontrar la raiz del vértice actual X
2 int Find( int x ){
3 if( x == padre[ x ] ){ //Si estoy en la raiz
4 return x; //Retorno la raiz
5}
6//else return Find( padre[ x ] ); //De otro modo busco el padre del
vértice actual, hasta llegar a la raiz.
7 else return padre[ x ] = Find( padre[ x ] ); //Compresion de caminos
8}
IMPLEMENTACIÓN DE UNIÓN POR RANGO
La idea de esta mejora básicamente lo que hará será unir el árbol de menor
rango a la raíz del árbol con el mayor rango, los rangos los almacenamos en un
arreglo y sufrirán modificación al momento de la unión. Los pasos para la
implementación son los siguientes:
1. Obtenemos la raíz del vértice x.
2. Obtenemos la raíz del vértice y.
3. Si el rango de X es mayor que el rango de Y entonces.
Actualizamos el padre de la raíz de Y asignándole como nuevo padre la
raíz de X.
4. De otro modo:
Actualizamos el padre de la raíz de X asignándole como nuevo padre la
raíz de Y.
Si los rangos de ambas raíces son iguales incremento el rango de la nueva
raíz en este caso incremento el rango de la raíz del vértice Y.
En resumen cada vez que hagamos unión entre dos componentes, la componente
de mayor altura rango) siempre predominara sobre la de menor altura ( rango ).
Veamos la inicialización:
17 de 26
Código:
1//Método de inicialización
2 void MakeSet( int n ){
3 for( int i = 0 ; i < n ; ++i ){
4 padre[ i ] = i; //Inicialmente el padre de cada vértice es el
mismo vértice
5 rango[ i ] = 0; //Altura o rango de cada vértice es 0
6 }
7}
VEÁMOSLO AHORA CON EJEMPLO ANTES VISTO
EN EL MÉTODO UNIÓN:
La imagen anterior muestra el caso de rangos iguales, por tanto aumentamos el
rango.
18 de 26
En este caso tenemos rangos diferentes, además no cumple con el paso 3
porque el rango del vértice 7 es 0 y no es mayor que el rango del vértice 0 que
es 1, al no tener rangos iguales los rangos quedan como estaban.
19 de 26
Este caso es similar al primero, por tanto el rango de la raíz de la componente
a la que pertenece el vértice Y se incrementa.
Caso similar a los anteriores con rangos iguales por parte de las raíces.
20 de 26
En la imagen anterior se hizo Union ( 6 , 4 ) -> Union( 8 , 4 ) -> en ese orden, las
actualizaciones las vemos en la tabla de la imagen.
Hasta el momento no hemos notado diferencia alguna entre la Unión normal con
la Unión por Rangos, haremos ahora Union (3, 6) por ambos métodos:
UNIÓN NORMAL.
21 de 26
La altura del nuevo árbol formado es de 3. Ahora veamos la diferencia con la
unión por rangos.
UNIÓN POR RANGO.
La altura del nuevo árbol es 2, este método mantiene el árbol tan balanceado
como sea posible, para mayor número de vértices se verá la diferencia en
cuanto a la eficiencia. Asimismo podemos decir que el rango del vértice raíz de
una componente conexa es la altura de dicha componente.
22 de 26
El código es el siguiente:
1. //Método para unir 2 componentes conexas usando sus alturas (rangos)
2. void UnionbyRank( int x , int y ){
3. int xRoot = Find( x ); //Obtengo la raiz de la componente del vértice X
4. int yRoot = Find( y ); //Obtengo la raiz de la componente del vértice Y
5. if( rango[ xRoot ] > rango[ yRoot ] ){ //en este caso la altura de la
componente del vértice X es
6. //mayor que la altura de la componente del vértice Y.
7. padre[ yRoot ] = xRoot; //el padre de ambas componentes será el
de mayor altura
8. }
9. else{ //en este caso la altura de la componente del vértice Y
es mayor o igual que la de X
10. padre[ xRoot ] = yRoot; //el padre de ambas componentes será el
de mayor altura
11. if( rango[ xRoot ] == rango[ yRoot ] ){ //si poseen la misma altura
12. rango[ yRoot ]++; //incremento el rango de la nueva raíz
13. }
14. }
15. }
NÚMERO DE COMPONENTES CONEXAS
Para saber el número de componentes conexas mediante unión-find, basta con
contar los vértices que sean raíces de su componente conexa, por ejemplo:
De la imagen podemos hallar la cantidad de componentes conexas de dos
formas:
23 de 26
Verificamos simplemente si padre[ x ] = x.
Verificamos si Find( x ) = x, al llamar a Find realizará la compresión de caminos.
En ambos casos será necesario recorrer el número de vértices y realizar la
verificación, en este ejemplo la respuesta será 4 componentes conexas.
Adicionalmente podemos almacenar la raíz de cada componente para usos
futuros.
Código:
1. int root[ MAX ]; //tendra las raices de las componentes conexas luego
de aplicar el método
2. int numComponentes; //variable para el numero total de componentes
conexas
3. //Método para obtener el numero de componentes conexas luego de
realizar las conexiones respectivas
4. int getNumberConnectedComponents( int n ){
5. numComponentes = 0;
6. for( int i = 0 ; i < n ; ++i ){
7. if( padre[ i ] == i ){ //Si el padre del vértice i es el mismo vértice
entonces es raíz
8. //if( Find( i ) == i ){ //podemos usamos find para el mismo proposito y
9. //para que se realice compresion de caminos
10. root[ numComponentes++ ] = i; //almaceno la raiz de cada nueva
componente
11. // numComponentes++;
12. }
13. }
14. return numComponentes;
24 de 26
15. }
CANTIDAD DE VÉRTICES POR COMPONENTE CONEXA.
Para saber la cantidad de Vértices que posee cada componente conexa basta
con tener un contador en la raíz de su componente conexa, de tal manera que al
recorrer cada vértice incrementamos el contador de la raíz de su componente
conexa. Veamos el siguiente ejemplo:
Comencemos haciendo Find( x ) desde vértice 0 hasta vértice 8:
Incrementamos en un arreglo el número de vértices, ello lo realizamos solo
sobre los vértices que son raíces:
1. for( int i = 0 ; i < n ; ++i ){
25 de 26
2. numVertices[ Find( i ) ]++; //incremento la raíz del vértice i
3. }
Código:
1. int numVertices[ MAX ]; //almacenara la cantidad de vértices para la i-
esima raiz.
2. //Método para obtener la raiz y el numero de vértices de cada
componente conexa
3. //será necesario primero tener la cantidad de componentes conexas
4. //podemos llamar 1ero al metodo getNumberConnectedComponents o
incluir porcion de su codigo en este
5. void getNumberNodes( int n ){
6. memset( numVertices , 0 , sizeof( numVertices ) ); //inicializo mi
contador de vértices
7. for( int i = 0 ; i < n ; ++i ){
8. numVertices[ Find( i ) ]++; //incremento la raíz del vértice i
9. }
10. for( int i = 0 ; i < numComponentes ; ++i ){
11. printf("Componente %d: Raiz = %d , Nro nodos = %d.\n" , i + 1 , root[ i ] ,
numVertices[ root[ i ] ] );
12. }
13. }
PROBLEMAS DE DIFERENTES JUECES.
1. UVA
2. TIMUS
3. TJU
4. POJ
Códigos:
Implementación de la estructura en C++:
Implementación de la estructura en JAVA:
Bibliografía 1 de 2
Por Jhosimar George Arias Figueroa
26 de 26
https://jariasf.wordpress.com/2012/04/02/disjoint-set-union-find/
Continúa… de la (Pág. 3).
COMO TRABAJA:
Primeramente ordenaremos las aristas del grafo por su peso de menor a mayor.
Mediante la técnica greedy Kruskal intentara unir cada arista siempre y cuando
no se forme un ciclo, ello se realizará mediante Union – Find. Como
hemos ordenado las aristas por peso comenzaremos con la arista de menor
peso, si los vértices que contienen dicha arista no están en la misma
componente conexa entonces los unimos para formar una sola componente
mediante Union(x , y), para revisar si están o no en la misma componente
conexa usamos la función SameComponent(x , y) al hacer esto estamos
evitando que se creen ciclos y que la arista que une dos vértices siempre sea la
mínima posible.
ALGORITMO EN PSEUDOCÓDIGO.
1 método Kruskal(Grafo):
2 inicializamos MST como vacío
3 inicializamos estructura unión-find
4 ordenamos las aristas del grafo por peso de menor a mayor.
5 para cada arista e que une los vértices u y v
6 si u y v no están en la misma componente
7 agregamos la arista e al MST
8 realizamos la unión de las componentes de u y v
Ejemplo y código pasó a paso
27 de 26
Tengamos el siguiente grafo no dirigido:
Como podemos ver en la imagen anterior la definición de nuestro grafo en
código sería:
1. struct Edge{
2. int origen; //Vértice origen
3. int destino; //Vértice destino
4. int peso; //Peso entre el vértice origen y destino
5. Edge(){}
6. …
7. }arista[ MAX ]; //Arreglo de aristas para el uso en Kruskal
Primeramente usaremos el método MakeSet de unión-find para inicializar cada
componente, obteniendo las siguientes componentes conexas iniciales:
Ahora el siguiente paso es ordenar las aristas del grafo en orden ascendente:
28 de 26
Para el ordenamiento podemos usar las librerías predefinidas de Java y C++
como estamos ordenando estructuras necesitamos un comparador, en este caso
estamos ordenando por peso por lo tanto dentro de la estructura antes
definida agregamos:
1. struct Edge{
2. …
3. //Comparador por peso, me servira al momento de ordenar lo realizara
en orden ascendente
4. //Cambiar signo a > para obtener el arbol de expansion maxima
5. bool operator<( const Edge &e ) const {
6. return peso < e.peso;
7. }
8. }arista[ MAX ]; //Arreglo de aristas para el uso en Kruskal
Ordenamos el arreglo de aristas mediante lo siguiente:
1. std::sort( arista , arista + E ); //Ordenamos las aristas por su
comparador.
29 de 26
Lo siguiente será recorrer todas las aristas ya ordenadas y verificar si sus
vértices están o no en la misma componente.
La primera arista a verificar es la que une a los vértices 8 y 7, verificamos si
están en la misma componente, para ello hacemos Find (8) , Find(7):
Como podemos observar en la tabla y en la misma imagen no están en la misma
componente conexa, por tanto esta arista es válida para el MST así que unimos
los vértices por el método de Union (8, 7).
30 de 26
Continuamos con la siguiente arista:
Observamos la tabla de Union-Find y vemos que Find (3) != Find(9). Entonces es
posible realizar la unión de ambas componentes:
Continuamos con la siguiente arista:
En la imagen podemos observar que ambos vértices no están en la misma
componente, por tanto realizamos la Union ( 6 , 7 ):
31 de 26
Continuamos con la siguiente arista, los vértices 1 y 2 no están en la misma
componente conexa:
Realizamos la Union(1,2):
Continuamos con la siguiente arista:
32 de 26
Al observar la imagen los vértices 3 y 6 están en distinta componentes
conexas. Entonces realizamos la Union(3,6) y actualizamos la tabla de Union-
Find.
Continuamos con la siguiente arista:
33 de 26
En este caso si observamos la imagen los vértices 7 y 9 están en la misma
componente conexa; asimismo en la tabla de Union-Find el elemento raíz del
vértice 7 es el mismo que el del vértice 9 por ello afirmamos que están el a
misma componente conexa, por lo tanto no habrá que realizar la unión de ambos
vértices. Con esto evitamos tener ciclos en el árbol de expansión mínima.
Continuamos con la siguiente arista:
Al observar la imagen los vértices 3 y 4 no están en la misma componente
conexa por lo tanto realizamos la Union(3,4) en el grafo:
Continuamos con la siguiente arista:
34 de 26
Los vértices 8 y 9 están en la misma componente conexa por lo tanto no
realizamos Unión de vértices. Continuemos con la siguiente arista:
Los vértices 1 y 8 están diferentes componentes. Realizamos la Union(1,8) en el
grafo:
35 de 26
Continuamos con la siguiente arista:
Los vértices 2 y 3 están en la misma componente conexa por lo tanto no
realizamos Union de componentes. Continuamos con la siguiente arista:
Los vértices 4 y 7 no están en la misma componente conexa, realizamos
Union(4,5) en el grafo:
36 de 26
Como podemos observar ya están todos los vértices del grafo conectados así
que al momento de continuar viendo las demás aristas ordenadas siempre
tendremos e l caso de que ya están en la misma componente conexa por lo tanto
el Árbol de Expansión Mínima para el grafo es el siguiente:
EL PESO TOTAL DEL ÁRBOL DE EXPANSIÓN MÍNIMA PARA EL GRAFO
MOSTRADO ES 39.
En código simplemente es iterar sobre el arreglo de aristas ingresado y
ordenado obteniendo sus respectivos datos. Para verificar si están o no en la
misma componente usamos el método sameComponent explicado en el tutorial
de Union-Find:
1. for( int i = 0 ; i < E ; ++i ){ //Recorremos las aristas ya ordenadas por
peso
2. origen = arista[ i ].origen; //Vértice origen de la arista actual
3. destino = arista[ i ].destino; //Vértice destino de la arista actual
4. peso = arista[ i ].peso; //Peso de la arista actual
5. //Verificamos si estan o no en la misma componente conexa
6. if( !sameComponent( origen , destino ) ){ //Evito ciclos
7. total += peso; //Incremento el peso total del MST
8. MST[ numAristas++ ] = arista[ i ]; //Agrego al MST la arista actual
9. Union( origen , destino ); //Union de ambas componentes en una sola
10. }
11. }
37 de 26
VERIFICACIÓN DE MST.
Para que sea un MST válido el número de aristas debe ser igual al número de
vértices – 1. Esto se cumple debido a que el MST debe poseer todos los
vértices del grafo ingresado y además no deben existir ciclos. Si vemos el
ejemplo antes explicado tenemos en el MST:
Número de Aristas = 8
Número de Vértices = 9
Cumple con lo dicho -> 9 – 1 = 8 por tanto tenemos un MST válido. Veamos otro
ejemplo teniendo como grafo ingresado lo siguiente:
Como podemos observar el grafo ingresado posee 2 componentes conexas, al
aplicar kruskal obtendremos los siguientes MST:
38 de 26
En la imagen podemos observar el MST luego de aplicar kruskal, sin embargo no
es un MST válido porque no tiene 1 componente conexa que posea todos los
vértices, comprobemos:
Número de Aristas = 7
Número de Vértices = 9
No cumple lo dicho inicialmente 9 – 1 != 7 por lo tanto tenemos un MST invalido.
En código basta con un if:
1. //Si el MST encontrado no posee todos los vértices mostramos mensaje
de error
2. //Para saber si contiene o no todos los vértices basta con que el numero
3. //de aristas sea igual al numero de vertices - 1
4. if( V - 1 != numAristas ){
5. puts("No existe MST valido para el grafo ingresado, el grafo debe ser
conexo.");
6. return;
7. }
Problemas de diferentes Jueces.
UVA
908 – Re-connecting Computer Sites
1208 – Oreon
10034 – Freckles
10462 – Is There A Second Way Left?
10600 – ACM contest and Blackout
10842 – Traffic Flow
11228 – Transportation System
11631 – Dark roads
11710 – Expensive subway
11733 – Airports
11747 – Heavy Cycle Edges
11857 – Driving Range
COJ
1016 – Freckles
1690 – Bad Cowtractors
TOPCODER
39 de 26
SRM 356 DIV2-1000 – RoadReconstruction
SRM 492 DIV2 – 1000 – TimeTravellingSalesman
HDU
1102 – Constructing Roads
POJ
2377 – Bad Cowtractors
2421 – Constructing Roads
TJU
2531 – Oreon
Códigos:
Implementación del algoritmo en C++: Algoritmo de Kruskal
Implementación del algoritmo en JAVA: Algoritmo de Kruskal
Por Jhosimar George Arias Figueroa.
Bibliografía 2 de 2
https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-
algoritmo-de-kruskal/
http://www6.uniovi.es/usr/cesar/Uned/EDA/Apuntes/TAD_apUM_04.pdf
https://www.uaeh.edu.mx/docencia/P_Presentaciones/icbi/asignatura/Cap6ARBOLES.pdf
Para la Presentación.
https://es.wikipedia.org/wiki/Algoritmo_de_Kruskal
https://es.wikipedia.org/wiki/Grafo
40 de 26
