Árbol de expansiÓn mÍnima: algoritmo de kruskal | algorithms and more

8/19/2019 ÁRBOL DE EXPANSIÓN MÍNIMA: ALGORITMO DE KRUSKAL | Algorithms and More

1/16

Algorithms and MoreBlog about programming!

ÁRBOL DE EXPANSIÓN MÍNIMA: ALGORITMO DE KRUSKALPublicado el abril 19, 2012| 15 comentarios

Antes de explicar directamente el algoritmo de Kruskal, comenzaré dando conceptos sobre que es un árbo

expansión mínima para entender mejor el problema.

Árbol de Expansión

Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y alg

(posiblemente todas) de las aristas de G. Al ser creado un árbol no existirán ciclos, además debe existir una entre cada par de vértices.

Un grafo puede tener muchos arboles de expansión, veamos un ejemplo con el siguiente grafo:

En la imagen anterior se puede observar que el grafo dado posee 3 arboles de expansión, dichos arboles cum

con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.

Árbol de Expansión Mínima

Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compu

por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemplo anterior le agregamos pesos a

https://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.wordpress.com/https://jariasf.files.wordpress.com/2012/04/spanning-tree.jpghttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#commentshttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/https://jariasf.wordpress.com/


2/16

aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.

El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los

conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).

Algoritmo de Kruskal

Para poder comprender el algoritmo de kruskal será necesario revisar primer el tutorial de Union-Find.

Como trabaja:

Primeramente ordenaremos las aristas del grafo por su peso de menor a mayor. Mediante la técnica greedy Kru

intentara unir cada arista siempre y cuando no se forme un ciclo, ello se realizará mediante Union-Find. C

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

https://jariasf.wordpress.com/2012/04/02/disjoint-set-union-find/https://jariasf.wordpress.com/2012/04/02/disjoint-set-union-find/https://jariasf.files.wordpress.com/2012/04/spanning-tree2.jpg


3/16

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 paso a paso

Tengamos el siguiente grafo no dirigido:

Como podemos ver en la imagen anterior la definición de nuestro grafo en código sería:

Primeramente usaremos el método MakeSet de unión-find para inicializar cada componente, obteniendo

siguientes componentes conexas iniciales:

!"#$%&'

!"#$%" )*+,- &'" ./0+,12 3345/607, ./0+,1 &'" *,8601.2 3345/607, *,8601. &'" 9,8.2 33:,8. ,16/, ,; ?-@ A@B/086BC DEF G2 33E//,+;. *, B/086B8 9B/B ,; H8. ,1 I/H8IB;

https://jariasf.files.wordpress.com/2012/04/grafo.jpg


4/16

Ahora el siguiente paso es ordenar las aristas del grafo en orden ascendente:

Para el ordenamiento podemos usar las librerías predefinidas de Java y C++ como estamos ordenando estruct

necesitamos un comparador, en este caso estamos ordenando por peso por lo tanto dentro de la estructura a

definida agregamos:

!"#$%&'

!"#$%" )*+,- A 33J.K9B/B*./ 9./ 9,8.L K, 8,/ %)'!" )*+, R, ? %)'!" - #+"$#' 9,8. Q ,S9,8.2 @

https://jariasf.files.wordpress.com/2012/04/tabla1.jpghttps://jariasf.files.wordpress.com/2012/04/kruskal0.jpg


5/16

Ordenamos el arreglo de aristas mediante lo siguiente:

Lo siguiente será recorrer todas las aristas ya ordenadas y verificar si sus vértices están o no en la mi

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,

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 e

arista es valida para el MST así que unimos los vértices por el método de Union( 8 , 7 ).

Continuamos con la siguiente arista:

T @B/086BC DEF G2 33E//,+;. *, B/086B8 9B/B ,; H8. ,1 I/H8IB;

! 86*UU8./6> B/086B L B/086B V ) ?2 33W/*,1BK.8 ;B8 B/086B8 9./ 8H 7.K9B/B*./

https://jariasf.files.wordpress.com/2012/04/kruskal2.jpghttps://jariasf.files.wordpress.com/2012/04/kruskal01.jpg


6/16

Observamos la tabla de Union-Find y vemos que Find(3) != Find(9). Entonces es posible realizar la unión de am

componentes:


En la imagen podemos observar que ambos vértices no están en la misma componente, por tanto realizamo

Union( 6 , 7 ):

https://jariasf.files.wordpress.com/2012/04/kruskal5.jpghttps://jariasf.files.wordpress.com/2012/04/kruskal4.jpghttps://jariasf.files.wordpress.com/2012/04/kruskal3.jpg


7/16

Continuamos con la siguiente arista, los vértices 1 y 2 no están en la misma componente conexa:

Realizamos la Union(1,2):




8/16

Al observar la imagen los vértices 3 y 6 están en distinta componentes conexas. Entonces realizamos la Union(3

actualizamos la tabla de Union-Find.


En este caso si observamos la imagen los vértices 7 y 9 están en la misma componente conexa; asimismo en la

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

misma componente conexa, por lo tanto no habrá que realizar la unión de ambos vértices. Con esto evitamos t

ciclos en el árbol de expansión mínima.




9/16

Al observar la imagen los vértices 3 y 4 no están en la misma componente conexa por lo tanto realizam

Union(3,4) en el grafo:


Los vértices 8 y 9 están en la misma componente conexa por lo tanto no realizamos Unión de vértices. Continue

con la siguiente arista:



10/16

Los vértices 1 y 8 están diferentes componentes. Realizamos la Union(1,8) en el grafo:


Los vértices 2 y 3 están en la misma componente conexa por lo tanto no realizamos Union de componentes.




11/16

Los vértices 4 y 7 no están en la misma componente conexa, realizamos Union(4,5) en el grafo:

Como podemos observar ya están todos los vértices del grafo conectados así que al momento de continuar vielas demás aristas ordenadas siempre tendremos e l caso de que ya están en la misma componente conexa p

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 d

Para verificar si están o no en la misma componente usamos el método sameComponent explicado en el tutoria



12/16

Union-Find:

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 debi

que el MST debe poseer todos los vértices del grafo ingresado y además no deben existir ciclos. Si vemos el ejem

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 g

ingresado lo siguiente:

Como podemos observar el grafo ingresado posee 2 componentes conexas, al aplicar kruskal obtendremo

siguientes MST:

!"#$%&'TX

!Y!!

,)#> &'" 0 Z Y 2 0 Q ) 2 VV0 ?- 33[,7.//,K.8 ;B8 B/086B8 =B ./*,1B*B8 9./ 9,8. ./0+,1 Z B/086BC 0 GS./0+,12 3345/607, ./0+,1 *, ;B B/086B B76HB; *,8601. Z B/086BC 0 GS*,8601.2 3345/607, *,8601. *, ;B B/086B B76HB; 9,8. Z B/086BC 0 GS9,8.2 33:,8. *, ;B B/086B B76HB; 334,/0\07BK.8 80 ,86B1 . 1. ,1 ;B K08KB 7.K9.1,16, 7.1,PB &,> ]8BK,J.K9.1,16> ./0+,1 L *,8601. ? ?- 33) ./0+,1 L *,8601. ?2 33a10.1 *, BKNB8 7.K9.1,16,8 ,1 H1B 8.;B

@@

https://jariasf.files.wordpress.com/2012/04/kruskal21.jpghttps://jariasf.wordpress.com/2012/04/02/disjoint-set-union-find/


13/16

En la imagen podemos observar el MST luego de aplicar kruskal, sin embargo no es un MST válido porque no t

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:

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

!"#$%&'

33_0 ,; D_` ,17.16/B*. 1. 9.8,, 6.*.8 ;.8


14/16

11710 – Expensive subway

11733 – Airports

11747 – Heavy Cycle Edges

11857 – Driving Range

COJ

1016 – Freckles

1690 – Bad Cowtractors

TOPCODER

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

http://algorithms-and-more.googlecode.com/files/Kruskal.javahttp://algorithms-and-more.googlecode.com/files/Algoritmo%20de%20Kruskal.cpphttp://acm.tju.edu.cn/toj/showp2531.htmlhttp://poj.org/problem?id=2421http://poj.org/problem?id=2377http://acm.hdu.edu.cn/showproblem.php?pid=1102http://community.topcoder.com/stat?c=problem_statement&pm=11049http://community.topcoder.com/stat?c=problem_statement&pm=7921http://coj.uci.cu/24h/problem.xhtml?abb=1690http://coj.uci.cu/24h/problem.xhtml?abb=1016http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2957http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2847http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2833http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2757


15/16

SHARE THIS:

Twitter Facebook 2

15 RESPUESTAS A “ÁRBOL DE EXPANSIÓN MÍNIMA: ALGORITMO DE KRUSKAL”

! "

Me gusta

Sé el primero en decir que te gusta.

!

Esta entrada fue publicada en Algorithms, Main y etiquetada graph, kruskal, minimum spanning tree, mst, unio

find. Guarda el enlace permanente.

azael sebastian lucio florido | diciembre 7, 2012 en 2:56 am | Responder

excelente trabajo bro muy bueno el blog, me gustaria que hablaras sobre bellman ford y dp saludos y

gracias por la informacion

Angel Larios | febrero 6, 2013 en 3:11 pm | Responder

como seria en el caso de empezar con el nodo 7 me dara lo mismo

jariasf | febrero 6, 2013 en 5:53 pm | Responder

A que parte te refieres??

Mauri Wilde | junio 11, 2013 en 10:05 pm | Responder

Mucha gracias! En serio me fuiste de mucha ayuda

Sigue con el buen trabajo!

jhomoh | septiembre 28, 2013 en 4:19 pm | Responder

como lo hago dinamicamente

Adrián | marzo 28, 2014 en 10:22 am | Responder

Te rifas solo vi el pseudocódigo y pude hacerlo (Y)

jaime | junio 14, 2014 en 2:38 pm | Responder

No funciona el codigo

jariasf | junio 15, 2014 en 12:57 pm | Responder

Que parte no funciona? Codigo JAVA o C++?

https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=75#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-75https://jariasf.wordpress.com/https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=73#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-73https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=64#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-64http://ferprogramming.blogspot.mx/https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=36#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-36https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=32#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-32https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=22#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-22https://jariasf.wordpress.com/https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=21#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-21https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=18#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-18https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/https://jariasf.wordpress.com/tag/union-find/https://jariasf.wordpress.com/tag/mst/https://jariasf.wordpress.com/tag/minimum-spanning-tree/https://jariasf.wordpress.com/tag/kruskal/https://jariasf.wordpress.com/tag/graph/https://jariasf.wordpress.com/category/main/https://jariasf.wordpress.com/category/algorithms/https://widgets.wp.com/likes/#https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?share=facebook&nb=1&nb=1https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?share=twitter&nb=1&nb=1


16/16

Crea un blog o un sitio web gratuitos con WordPress.com. El tema Coraline.

welington | junio 22, 2014 en 5:04 pm | Responder

Muy bueno el codigo, pero como haria para por el input en un “file.txt” ?

Rolando | diciembre 14, 2014 en 5:56 pm | Responder

COMO ACCEDER AL REVOLUCIONARIO DE UVA mas que todo al problema oreony otros problemas.

Rolando | diciembre 14, 2014 en 5:56 pm | Responder

perdon al solucionario

jariasf | diciembre 15, 2014 en 9:41 am | Responder

No hay solucionario oficial de UVA. Si tienes dudas sobre algo puedes consultar en sus foros:

http://online-judge.uva.es/board/viewtopic.php?f=61&t=76006

Como casos de prueba, errores en codigo, etc.

Pepe | enero 26, 2015 en 8:34 pm | Responder

que buen tutorial, si no te molesta me gustaría usarlo para explicar MST a mis alumnos

jariasf | enero 26, 2015 en 8:40 pm | Responder

Gracias, usalo donde desees para eso estamos para ayudar

Santiago Mesa Mosquera | junio 8, 2015 en 4:12 pm | Responder

Muchas gracias, esta excelente este articulo y todo su bloc es espectacular, demasiado útil, lo felicito.
https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=124#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-124https://plus.google.com/116886106047512473977https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=117#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-117https://jariasf.wordpress.com/https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=116#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-116http://gravatar.com/gabriel071993http://online-judge.uva.es/board/viewtopic.php?f=61&t=76006https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=111#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-111https://jariasf.wordpress.com/https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=110#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-110https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=109#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-109https://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/?replytocom=76#respondhttps://jariasf.wordpress.com/2012/04/19/arbol-de-expansion-minima-algoritmo-de-kruskal/#comment-76https://wordpress.com/themes/coraline/https://es.wordpress.com/?ref=footer_website

Árbol de expansiÓn mÍnima: algoritmo de kruskal | algorithms and more

Documents