Como encontrar o Minimal Spanning Tree de um grafo usando o algoritmo de Kruskal?

Question

Discuta e implemente a solução para o problema de encontrar a Minimal Spanning Tree de um grafo usando o algoritmo ganancioso Kruskal’s algoritm. Justifique (prove) cuidadosamente essa estratégia gananciosa.

Answer 1

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:

1. Inicializar o conjunto "minimumspanningtree_edges" como vazio;
2. Criar \(|V|\) árvores, cada uma contendo um vértice;
3. Ordenar as arestas em ordem não-decrescente de peso;
4. 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.