Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

+1 voto
1,523 visitas
perguntada Mai 18, 2016 em Ciência da Computação por Caue (231 pontos)  
Compartilhe

1 Resposta

+1 voto
respondida Mai 18, 2016 por Caue (231 pontos)  
 
Melhor resposta

Para resolver o problema de encontrar a Árvore Geradora Mínima (Minimal Spanning Tree) de um grafo, foi implementado o algoritmo de Prim, baseado no capítulo 9.1 do livro Introduction to the Design and Analysis of Algorithms, de Anany Levitin.

A função recebe como parâmetros o grafo no qual será feita a busca da árvore geradora mínima e o vértice de origem para a busca (o vértice de origem escolhido não interfere no resultado). Ao final da execução, será retornada uma lista com as arestas selecionadas e o peso final da árvore, que deve ser a árvore com o menor peso possível contendo todos os vértices originais interligados.

A partir do vértice inicial, por ser um algoritmo ganancioso, procuramos um vértice conectado a esse com a aresta de menor custo. Ao encontrar esse vértice, guardamos a aresta na lista de solução e juntamos esse vértice ao vértice inicial.

Agora procuramos um vértice conectado a um desses dois vértices (pode ser qualquer um dos dois) com a aresta de menor custo. Ao encontrar, guardamos a aresta na lista de solução e juntamos esse terceiro vértice aos dois vértices anteriores.

O processo é repetido até que tenhamos feito isso para cada vértice do grafo.

Ou seja, o algoritmo começa com uma sub-árvore contendo apenas o primeiro vértice e vai expandindo essa sub-árvore, escolhendo sempre o vértice mais próximo que ainda não esteja nela.


A implementação foi feita em python 3.5.1, e o código é apresentado a seguir:

def prim(graph, root):
    vertex = [root]  # Lista dos vertices a partir do qual buscamos as arestas
    selected_edges = []  # Lista com as arestas selecionadas

    weight = 0  # Peso do minimum spanning tree

    remaing_vertices = list(graph.vertices())  # Lista com os vertices destinos da busca
    remaing_vertices.remove(root)  # O root eh ponto de partida, entao sai da lista

    for i in range(len(remaing_vertices)):  # Devemos buscar |V| - 1 vertices
        min_cost = inf  # Inicializamos o custo minimo como infinito
        va, vb = None, None  # Vertices candidatos para a aresta selecionada
        for v1 in vertex:  # Para cada vertice na lista de busca origem
            for v2 in remaing_vertices:  # Buscamos os vertices que ainda nao estao no grafo final
                cost = graph.direct_cost(v1, v2)  # Calcula o custo da aresta
                if cost < min_cost:  # Se for menor que o minimo ate entao, atualizamos os dados
                    va = v1
                    vb = v2
                    min_cost = cost

        if min_cost < inf:  # Depois de todas as buscas, se o custo eh finito:
            selected_edges.append((va, vb, min_cost))  # Adicionamos a aresta de va a vb na solucao
            vertex.append(vb)  # vb agora sera nova origem de busca
            remaing_vertices.remove(vb)  # vb nao mais sera destino de busca, pois ja consta na solucao
            weight += min_cost  # Atualiza o peso

    return selected_edges, weight  # Retorna a lista de arestas selecionadas com o peso total

Para o grafo a seguir, a execução do algoritmo retorna o seguinte resultado:

A imagem será apresentada aqui.

Arestas selecionadas:

a-h Custo: 5
h-b Custo: 13
h-f Custo: 13
f-g Custo: 1
f-c Custo: 2
g-d Custo: 8
g-e Custo: 12

Peso total: 54

Grafo com as arestas selecionadas:
A imagem será apresentada aqui.


Código completo disponível em:
https://gist.github.com/cauemello/208625ce41b61655d4db76f54f1d7fe5

...