O algoritmo de Prim é um dos mais famosos da Teoria dos Grafos. Por meio dele podemos fazer uma árvore geradora mínima de um grafo.
Para isso Prim utiliza-se de uma lista de prioridades baseada no peso de cada aresta.
Dessa maneira, para facilitar o desenvolvimento de uma Ávore Geradora Mímina iremos mostrar um tutorial de como codificar Prim para Phyton:
Inicialmente, foi escolhido um grafo NÃO direcionado e com peso, uma vez que tais atributos são pré-requisitos para extraírmos a MST. Portanto, o dataset é relativo a este site: https://toreopsahl.com/datasets/#southernwomen em que se foi escolhido o dataset 13 "Davis Southerm Women Club".
Plotando o grafo em seu estado inicial obtivemos o seguinte grafo:
FIGURA 1: Grafo das Davis Southerm Women Club
Com isso, inciou-se o desenvolvimento da função Prim:
FIGURA 2: Primeira parte da função Prim
Nessa FIGURA 2 é possível verificar que foi implementado um dicionário chamado Predecessor. Tal dicionário é responsável por guardar o mapa/tabela de predecessores de cada vértice visitado. Dessa maneira é configurado de maneira (x:y) em que x é um vértice e y seu predecessor.
Além disso, conforme o algoritmo todos os vértices, exceto o da raiz que tem por peso 0, inicia a lista de prioridades com valor infinito e precessor igual a None, ou seja, não possui predecessor.
Em substituição a lista de vertices visitados e evitar ficar comparando com o grafo, utilizamos este próprio como a lista. Assim após passar por um vértice esse é excluído do grafo.
É possível verificar na imagem também a função que extrai o vértice de peso mínimo, que é feita pela simples comparação com todos os vértices.
FIGURA 3: Segunda parte do algoritmo
Na FIGURA 3 é possível identificar a troca de predecessor na linha 37 ao verificar-se nos vizinhos e inserção no dicionário de predecessores na linha 41.
Além disso, ao final do algoritmo é gerado e impresso seu mapa de predecessores conforme linhas 46 e 47 além de plotar novo grafo a partir do próprio dicionário nas linhas 49 - 67
Na FIGURA 4 será possível ver a instanciação dos objetos, assim como a passagem de parâmetros.
FIGURA 4: "Main" do programa
Como resultados obtivemos a FIGURA 5 como raiz e mapa de predecessores e na FIGURA 6 a MST plotada.
FIGURA 5: Mapa de predecessores da MST
FIGURA 6: MST gerada conforme mapa de predecessores
Nenhum comentário:
Postar um comentário