Algoritmo de Prim: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Consertando a conexidade |
|||
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]]
__TOC__
==Descrição==
| |||