O algoritmo de Prim

O algoritmo de Prim acha a árvore geradora mínima de maneira gulosa: começa com um único vértice na árvore e, a cada passo, adiciona o vértice que se liga a árvore através da menor aresta até que todas os vértices do grafo tenham sido incluídos. A estratégia é gulosa já que a cada passo é adiciona a aresta de menor peso que liga um vértice que está na árvore a um vértice que não está. De maneira geral, podemos descrever o algoritmo de Prim segundo o seguinte pseudo-código:
MST-Prim(G, r): # acha a árvore geradora do grafo G começando do vértice r árvore resultado T = { r } enquanto T tiver menos que |V| vértices: encontrar o vértice x que ainda não está na árvore e que se liga a qualquer T pela menor aresta T = T U { x }
O problema é, então, manter uma estrutura que indique quais vértices estão (ou não) na árvore e que permita acessar facilmente, a cada passo, qual o vértice que não está na solução mais próximo da árvore sendo gerada. Podemos então refinar ainda mais o pseudo-código para o seguinte:
MST-Prim(G, r): # acha a árvore geradora do grafo G começando do vértice r MenorDistancia[1..|V|] = INFINITO MenorDistancia[r] = 0 Arvore = { r } Enquanto Arvore tiver menos que |V| vértices: x = achar o vertice que nao esta em Arvore e que tem o menor valor de MenorDistancia Arvore = Arvore U { x } Para cada vizinho u de x: Se u não está em Arvore E a MenorDistancia[ u ] > peso(x,u), faça: MenorDistancia[ u ] = peso(x,u)
Análise de corretude
Uma excelente análise da corretude do algoritmo explicado acima encontra-se no livro "Introduction to Algorithms" de Cormen et. al, descrevemos a seguir uma versão resumida. O algoritmo de Prim começa com uma árvore contendo somente um único nó (logo mínima, porém ainda não geradora) e, a cada passo, mantém a invariante de que a árvore sendo criada é mínima, através do seguinte teorema (cuja prova