Projeto 2: Árvore Geradora Mínima

MST - Minimum Spanning Tree

Uma MST (Árvore Geradora Mínima) de um grafo G, é qualquer árvore geradora de G que tenha o menor custo. Ou seja, uma árvore geradora de G é mínima se nenhuma outra árvore geradora tenha custa menor do que ela.

Objetivos

A partir de um dataset específico (grafo ponderado armazenado em arquivo .txt) implementar o algoritmo de Prim para extrair uma Minimum Spanning Tree (MST) do grafo G abaixo.

Grafo com 30 cidades do mundo

Algoritmo de Prim

O algoritmo de Prim tem como característica a cada passo de execução criar uma subárvore, até que ela se torne a geradora.
A implementação em Python pode ser visualizada abaixo:

Metodologia

Foi utilizada a linguagem de programação Python e as bibliotecas NumPy, NetworkX e Matplotlib para gerar o desenho do grafo.
O MST do grafo G pode ser visto abaixo:

MST do grafo G