Revisão das 13h35min de 29 de agosto de 2013 editar Kaktus Kid (discussão \| contribs) 218 630 edições Ajustes ← Ver a alteração anterior		Revisão das 13h40min de 29 de agosto de 2013 editar desfazer Kaktus Kid (discussão \| contribs) 218 630 edições Ajuste Ver a alteração posterior →
Linha 1: Na [[ciência da computação]] o '''algoritmo de Prim''' é um [[algoritmo guloso]] (''greedy algorithm'') empregado para encontrar uma [[árvore geradora mínima]] (''minimal spanning tree'') num grafo conectado, valorado e não direcionado. Isso significa que o algoritmo encontra um subgrafo do grafo original no qual a soma total das arestas é minimizada e todos os vértices estão interligados. O algoritmo foi desenvolvido em 1930 pelo matemático [[Vojtěch Jarník]] e depois pelo cientista da computação [[Robert Clay Prim]] em 1957 e redescoberto por [[Edsger Dijkstra]] em 1959. Outros algoritmos conhecidos para encontrar [[árvore geradora mínima\|árvores geradoras mínimas]] são o [[algoritmo de Kruskal]] e [[algoritmo de Boruvka]]. No entanto estes algoritmos podem ser empregados em grafos desconexos, enquanto o '''algoritmo de Prim''' precisa de um grafo conexo.

Algoritmo de Prim: diferenças entre revisões