Solução Reduzindo Detalhes em um Mapa – Semana 1

Solução por Lucca Siaudzionis

Este problema é um clássico que consiste em: dado um grafo, encontrar sua Árvore Geradora Mínima (mais conhecida pelo nome, em inglês, Minimum Spanning Tree ou MST). Há dois algoritmos muito conhecidos para resolver esse tipo de problema:

• Algoritmo de Kruskal
• Algoritmo de Prim

Eu, por preferência pessoal, uso o Algoritmo de Kruskal, e aqui está meu código no problema:

https://gist.github.com/luccasiau/4faf910fa9d4294f087c

Aqui está o código do problema usando o Algoritmo de Prim, para quem tiver curiosidade:

https://gist.github.com/luccasiau/1f41cfc20dfa22d03195