Introduction

Bem-vindo ao curso final da série Algoritmos de Grafos! Assim como Kruskal, o Algoritmo de Prim constrói uma Árvore Geradora Mínima: o conjunto mais barato de arestas que conecta todos os vértices sem um ciclo. Os dois algoritmos chegam à mesma resposta por caminhos diferentes.

Prim expande a árvore a partir de um vértice inicial. A cada passo, ele adiciona a única aresta mais barata que conecta a árvore a um vértice que ainda não faz parte dela.

O grafo é não direcionado e ponderado, fornecido como n (vértices 0 a n - 1) e edges, um array unidimensional de triplas [u0, v0, w0, ...] para uma aresta não direcionada u - v de peso w. Começamos pelo vértice 0.

Vamos terminar a série!