El algoritmo Kruskal genera el Árbol de Cobertura Mínima de un gráfico conexo. ¿Pero qué es un árbol de cobertura mínima? Supongamos que tenemos un grafo, y queremos reducir su complejidad para poder trabajar con el. Este grafo tiene pesos, por lo tanto tratamos de encontrar un árbol que pueda cubrir todos sus nodos, pero que tenga como característica utilizar los mínimos pesos para todas los arcos. La sigueinte gráfica mostrará la ídea general de este algoritmo:

El grafo es conexo y tiene pesos. Un MST es un árbol generado a partir de este grafo que utilice tódos los nodos, pero que se conecte por medio de los arcos que tengan el mínimo peso. Imágen tomada de: Wikimedia Commons

 

Para ello existen dos algoritmos ampliamente usados, que si bien no son los óptimos, son una introducción para resolver este problema. Tenemos a Kurskal y Prim. En esta ocación hablaremos de Kruskal. 

Para ello funciona de la siguiente manera:

A=∅
for all vértice v ∈ G.V do
   Hacer-Conjunto(v)
end for
ordena las aristas de G.E en un orden no decreciente por el peso w.
for all arista(u, v) ∈ G.E, tomado en orden no decreciente por peso do
   if Encontrar-Conjunto(u) = Encontrar-Conjunto(v) then
       A = A ∪ (u, v)
       Unión (u, v)
   end if
end for
return A

Su diagrama de flujo es:

 

Y aquí una implementación en Python:

# -*- coding:utf-8 -*-
# Implementación del algoritmo Kruskal

# Variables globales
base = dict()
ord = dict()   

# Función para generar conuntos
def make_set(v):
    base[v] = v
    ord[v] = 0

# Implementación de la función de búsqueda 
# de manera recursiva
def find(v):
    if base[v] != v:
        base[v] = find(base[v])
    return base[v]

# Implementación de la unión de conjuntos
def union(u, v):
    v1 = find(u)
    v2 = find(v)
    if v1 != v2:
        if ord[v1] > ord[v2]:
            base[v2] = v1 
        else:
            base[v1] = v2
            if ord[v1] == ord[v2]: 
                ord[v2] += 1

# Función principal del algoritmo Kruskal
def kruskal(graph):

    # A = {conjunto vacío}
    mst = set()
   
    # Para todo vértice v en G.V
    for v in graph['vertices']:
        make_set(v)
    print "Sub gráficos creados:"
    print base

    # Ordena la lista G.E en forma no decendente por su peso w
    # En este caso usamos el ordenador dentro de python
    edges = list(graph['edges'])
    edges.sort()
    
    print "Aristas ordenadas:"
    print edges

    # Para toda arista(u,v) en G.E
    for e in edges:
        weight, u, v = e
        # Si encontrar-conjunto(u) != encontrar-conjunto(v)
        if find(u) != find(v):
            # A = A union (u,v)
            union(u, v)
            # Union(u,v)
            mst.add(e)
    return mst 

graph = {
'vertices': ['a','b','c','d','e','f'],
'edges': set([
    (5,'a','c'),
    (3,'a','d'),
    (2,'b','d'),
    (1,'c','d'),
    (5,'f','d'),
    (3,'b','f'),
    (6,'f','e'),
    (1,'a','b'),
    ])
}

k = kruskal(graph)
print "Resultado MST:"
print k

 

Share This