Download El algoritmo de Kruskal es un algoritmo de la teoría de grafos para

CARLOS ALBERTO ALVAREZ
904501
Algoritmo de Kruskal
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un
árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un
subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde
el valor total de todas las aristas del árbol es el minimo. Si el grafo no es conexo,
entonces busca un bosque expandido mínimo (un árbol expandido mínimo para
cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo
voraz.
Funciona de la siguiente manera:



se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo
es un árbol separado
se crea un conjunto C que contenga a todas las aristas del grafo
mientras C es novacío
o eliminar una arista de peso mínimo de C
o si esa arista conecta dos árboles diferentes se añade al bosque,
combinando los dos árboles en un solo árbol
o en caso contrario, se desecha la arista
Al acabar el algoritmo, el bosque tiene una sola componente, la cual forma un
árbol de expansión mínimo del grafo.
Pseudocódigo
1 function Kruskal(G)
2 for each vertex v in G do
3
Define an elementary cluster C(v) ← {v}.
4 Initialize a priority queue Q to contain all edges in G, using the weights as
keys.
5 Define a tree T ← Ø
//T will ultimately contain the edges of the MST
6 // n es el número total de vértices
7 while T has fewer than n-1 edges do
8
// edge u,v is the minimum weighted route from/to v
9
(u,v) ← Q.removeMin()
10
// previene ciclos en T. suma u,v solo si T no contiene una arista que una u y
v.
11
// Nótese que el cluster contiene más de un vértice si una arista une un par
de
12
// vértices que han sido añadidos al árbol.
13
Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.
14
if C(v) ≠ C(u) then
15
Add edge (v,u) to T.
16
Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).
17 return tree T
Ejemplo
Este es el grafo original. Los números de las
aristas indican su peso. Ninguna de las aristas está
resaltada.
AD y CE son las aristas mas cortas, con peso 5, y
AD se ha elegido arbitrariamente, por tanto se
resalta.
Sin embargo, ahora es CE la arista mas pequeña
que no forma ciclos, con peso 5, por lo que se
resalta como segunda arista.
La siguiente arista, DF con peso 6, ha sido
resaltada utilizando el mismo método.
La siguientes aristas mas pequeñas son AB y BE,
ambas con peso 7. AB se elige arbitrariamente, y
se resalta. La arista BD se resalta en rojo, porque
formaría un ciclo ABD si se hubiera elegido.
El proceso continúa marcando las aristas, BE con
peso 7. Muchas otras aristas se marcan en rojo en
este paso: BC (formaría el ciclo BCE), DE
(formaría el ciclo DEBA), y FE (formaría el ciclo
FEBAD).
Finalmente, el proceso termina con la arista EG de
peso 9, y se ha encontrado el árbol expandido
mínimo.