Toda "spanning tree" possui \(|V|-1\) vértices [1, p. 624], pelo Teorema B.2 de [1, p. 1174]. Portanto, no problema do "minimum spanning tree", devemos encontrar a "spanning tree" com peso mínimo.
Existem algumas versões do algoritmo Kruskal, como em [1, p. 631-633] e [2, p. 325-327]. Esta solução implementará esta primeira referência.
O algoritmo pode ser resumido pelos seguintes passos:
- Inicializar o conjunto "minimumspanningtree_edges" como vazio;
- Criar \(|V|\) árvores, cada uma contendo um vértice;
- Ordenar as arestas em ordem não-decrescente de peso;
- Para cada aresta \((u,v)\), que está ordenada de forma não-decrescente pelo peso, checa-se se u e v pertencem a mesma árvore. Se pertencerem, adicionar a aresta \((u,v)\) implica na criação de um ciclo, portanto, a aresta é descartada. Caso contrário, os vértices u e v pertencem a árvores diferentes, então adiciona-se o vértice à variável "minimumspanningtree_edges" e, em seguida, mescla-se os vértices das duas árvores.
O algoritmo de Kruskal é uma estratégia gananciosa, pois, a cada iteração, adiciona-se à "floresta" uma aresta com o menor peso possível. A prova formal deste algoritmo segue os mesmos passos de [2, p. 320].
A implementação desse algoritmo é feita pela função "kruskal", que segue fielmente os passos do algoritmo. A função recebe-se como parâmetro o grafo e retorna as arestas que compõe a "minimum spanning tree" e o peso final da árvore. Tentou-se utilizar a mesma estrutura de dados do algoritmo Prim apresentado em outro post do Prorum, implementada por Cauê. Para testar o algoritmo, utilizou-se o mesmo exemplo deste post. Os códigos-fontes em Python 2.7 são mostrados a seguir.
Código-fonte (Python 2.7)
Arquivo "Graph.py". O arquivo original, implementado por Cauê, foi adaptado para Python 2.7, e também acrescentou-se um "construtor de cópia", conforme código mostrado abaixo:
import copy
# Implementacao de Grafo baseada em http://www.python-course.eu/graphs_python.php
class Graph(object):
def __init__(self, graph_dict={}):
if (isinstance(graph_dict, Graph)):
self.__graph_dict = copy.deepcopy(graph_dict.__graph_dict)
else:
self.__graph_dict = graph_dict
def vertices(self):
return list(self.__graph_dict.keys())
def edges(self):
return self.__generate_edges()
def add_vertex(self, vertex):
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] = []
def add_edge(self, edge, bidirectional=True):
(vertex1, vertex2, cost) = edge
self.add_vertex(vertex1)
self.add_vertex(vertex2)
self.__add_edge_no_repetition(vertex1, vertex2, cost)
if bidirectional:
self.__add_edge_no_repetition(vertex2, vertex1, cost)
def direct_cost(self, vertex1, vertex2):
list_v1 = self.__graph_dict[vertex1]
for (v, cost) in list_v1:
if v == vertex2:
return cost
else:
return float('inf')
def __add_edge_no_repetition(self, v1, v2, cost):
list_v1 = self.__graph_dict[v1]
for i, (v, _) in enumerate(list_v1):
if v == v2:
list_v1[i] = (v2, cost)
break
else:
list_v1.append((v2, cost))
def __generate_edges(self):
edges = []
for vertex in self.__graph_dict:
for (neighbour, cost) in self.__graph_dict[vertex]:
if (neighbour, vertex) not in edges:
edges.append((vertex, neighbour, cost))
return edges
def __str__(self):
return 'Vertices: {0}\nEdges: {1}'.format(sorted(self.vertices()), sorted(self.edges()))
Arquivo "GraphUtils.py", utilizado o arquivo original implementado pelo Cauê.
Arquivo "kruskal.py", que contém o algoritmo Kruskal. As implementações de "makeset", "findset" e "union" seguem os algoritmos em [1, p. 571].
from Graph import Graph
from GraphUtils import print_graph
from operator import itemgetter
class KruskalGraph(Graph):
def __init__(self, graph_dict={}):
Graph.__init__(self, graph_dict)
self.parent = dict()
self.rank = dict()
return
def make_set(self, vertex):
self.parent[vertex] = vertex
self.rank[vertex] = 0
return
def find_set(self, vertex):
if (self.parent.has_key(vertex) and (self.parent[vertex] != vertex)):
self.parent[vertex] = self.find_set(self.parent[vertex])
return self.parent[vertex]
def union(self, vertex1, vertex2):
root1 = self.find_set(vertex1)
root2 = self.find_set(vertex2)
if (root1 != root2):
if (self.rank[root1] > self.rank[root2]):
self.parent[root2] = root1
else:
self.parent[root1] = root2
if (self.rank[root1] == self.rank[root2]):
self.rank[root2] += 1
return
def kruskal(self):
minimum_spanning_tree_edges = set()
minimum_spanning_tree_weight = 0
for vertex in self.vertices():
self.make_set(vertex)
edges = sorted(self.edges(), key=itemgetter(2))
for edge in edges:
(u, v, weight) = edge
if (self.find_set(u) != self.find_set(v)):
minimum_spanning_tree_edges.add(edge)
minimum_spanning_tree_weight += weight
self.union(u, v)
return minimum_spanning_tree_edges, minimum_spanning_tree_weight
def kruskal(graph):
return KruskalGraph(graph).kruskal()
Código de teste:
if __name__ == '__main__':
g = Graph({})
edges = [('a', 'b', 17), ('a', 'e', 14), ('a', 'h', 5), ('b', 'g', 18), ('b', 'h', 13), ('c', 'e', 20),
('c', 'f', 2), ('d', 'e', 19), ('d', 'g', 8), ('e', 'g', 12), ('f', 'g', 1), ('f', 'h', 13)]
for e in edges:
g.add_edge(e)
kruskal_edges, kruskal_weight = kruskal(g)
g_kruskal = Graph({})
for e in kruskal_edges:
g_kruskal.add_edge(e, False)
print_graph(g_kruskal)
print('Grafo Original:\n%s' % g)
print('--')
print('Minimal Spanning Tree - Kruskal (Peso Final = %s):\n%s' % (kruskal_weight, g_kruskal))
Resultados
Arestas da "minimum spanning tree":
a-h Custo: 5
b-h Custo: 13
c-f Custo: 2
d-g Custo: 8
e-g Custo: 12
f-h Custo: 13
g-f Custo: 1
Peso total: 54
Grafo com as arestas da "minimum spanning tree":

Referências:
[ 1 ] Cormen, T. H.; Leiserson, C. E.; Rivest, R.; Stein, C. "Introduction to Algorithms". MIT Press, 2009. 3 ed.
[ 2 ] Levitin, A. "Introduction to the design and analysis of algorithms". Pearson, 2011. 3 ed.