Algoritmo de Prim

Este algoritmo é usada para gerar as chamadas Minimal Spanning Tree (MST). Para falarmos mais disso primeiramente vamos definir o que é uma árvore.
- G é um grafo;
- G é acíclico se não contém ciclos;
- G é uma árvore se for acíclico e conexo.

Para este algoritmo vale lembrar que é preciso um grafo que contenha peso nas arestas (grafo ponderado). Encontrar uma MST consiste que se escolha um vértice inicial, em cada passo se escolha uma aresta de menor peso, que respeite a regra de não formar ciclos, até passar por todos os vértices.
Embaixo temos uma imagem que representa como o algoritmo funciona.

Então para que esse algoritmo seja feito primeiro vamos usar uma primitiva que pega o menor valor de um conjunto:

Agora o algoritmo implementado:

Na linha 64, 65, 66 e 67 é onde ocorre a lógica principal do algoritmo que verifica se o valor de um vértice é maior que a aresta que estamos observando para atingir este mesmo nó. Se for maior que dizer que compensa ir na aresta porque queremos o menor valor.
Abaixo temos uma foto que mostra o resultado obtido quando usamos este algoritmo.

Fontes e ferramentas:

https://pt.wikipedia.org/wiki/Algoritmo_de_Prim;
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/prim.html;

Notas de aula da matéria;

Python(x,y);

Spyder Python.