Revisão das 20h18min de 31 de agosto de 2008 editar VolkovBot (discussão \| contribs) Robôs 277 687 edições m Bot: Adicionando: ja:プリム法 ← Ver a alteração anterior		Revisão das 07h29min de 8 de setembro de 2008 editar desfazer Leonardo.stabile (discussão \| contribs) 78 149 edições *fmt Ver a alteração posterior →
Linha 1: [[Imagem:Prim.PNG\|\|thumb\|Passo a passo da execução do '''algoritmo de Prim''']] O '''algoritmo de Prim''' é um [[algoritmo]] em [[teoria dos grafos]] que busca uma [[árvore geradora mínima]] para um [[grafo]] [[Conexidade\|conexo]] com pesos. O algoritmo de Prim é um exemplo de um [[algoritmo guloso]]. ~~<li>~~* O subconjunto <math>S</math> forma uma única árvore, e a aresta segura adicionada a <math>S</math> é sempre uma aresta de peso mínimo conectando a árvore a um vértice que não esteja na árvore.~~</li>~~ ~~<li>~~* A árvore começa por um vértice qualquer e cresce até que "gere" todos os vértices em <math>V</math>.~~</li>~~ ~~<li>~~* A cada passo, uma aresta leve é adicionada à árvore <math>S</math>, conectando <math>S</math> a um vértice de <math>G_{S} = ( V ; S )</math>.~~</li>~~ ~~<li>~~* De acordo com o teorema anterior, quando o algoritmo termina, as arestas em <math>S</math> formam uma árvore geradora mínima.~~</li>~~ A ordem de complexidade para o algoritmo de Prim é <math> O(\|E\|\log \|V\| ) \,\!</math>, ~~onde~~em que <math>E</math> é o conjunto de arestas e <math>V</math> é o conjunto de vértices do grafo. == Implementação em PHP == <source lang="php"> ~~== Algoritmo implementado em PHP ==~~ $origem = array(1 => 1,1,2,2,2,3,4,4,5); $destino = array(1 => 2,3,3,4,5,5,6,5,6); Linha 118 ⟶ 116: echo "\n V: "; print_r($v);} </source> {{esboço-programação}} [[Categoria: Algoritmos de grafos\|Prim]] ~~[[Categoria: Teoria dos grafos\|Prim]]~~ [[cs:Jarníkův algoritmus]]

Algoritmo de Prim: diferenças entre revisões