Revisão das 09h53min de 23 de dezembro de 2015 editar 2001:8a0:ff72:d701:d78:fe30:3bd:7de9 (discussão) Função PRIM em C Etiqueta: Editor Visual ← Ver a alteração anterior		Revisão das 16h42min de 16 de abril de 2016 editar desfazer 177.142.50.248 (discussão) Etiquetas: Edição via dispositivo móvel Edição feita através do sítio móvel 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. __TOC__ ==Descrição== [[Imagem:Prim.PNG\|thumb\|250px\|direita\|Figura 1: passo a passo da execução do '''algoritmo de Prim''' iniciado pelo vértice 0]]

Algoritmo de Prim: diferenças entre revisões