Algoritmo de Prim: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m r2.7.2) (Robô: A adicionar: mk:Примов Алгоритам |
|||
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 C. 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==
[[Ficheiro:Prim.PNG|thumb|250px|direita|Figura 1: passo a passo da execução do '''algoritmo de Prim''' iniciado pelo vértice 0]]
O '''algoritmo de Prim''' encontra uma [[árvore geradora mínima]] para um grafo desde que ele seja valorado e não direcionado. Por exemplo, se na ''figura 1'' os vértices deste grafo representassem cidades e as arestas fossem estradas de terra que interligassem estas cidades, como poderíamos determinar quais estradas asfaltar gastando a menor quantidade de asfalto possível para interligar todas as cidades. O '''algoritmo de Prim''' neste caso fornecerá uma resposta ótima para este problema que não necessariamente é única. A etapa ''f)'' da figura 1 demonstra como estas cidades devem ser conectadas com as arestas em negrito.
===Algoritmo genérico===
Um algoritmo genérico para o '''algoritmo de Prim''' é dado da seguinte forma:
:''Escolha um vértice '''S''' para iniciar o subgrafo''
:: '''''enquanto''' há vértices que não estão no subgrafo''
::: ''selecione uma aresta segura''
::: ''insira a aresta segura e seu vértice no subgrafo''
==Complexidade==
A complexidade do algoritmo de Prim pode mudar de acordo com a estrutura de dados utilizada para representar o grafo. As implementações mais comuns para um grafo são por [[lista de adjacência|listas de adjacência]] e por [[matriz de adjacência|matrizes de adjacência]] e suas respectivas complexidades <math>O(|V|log|A|)</math> e <math>O(V^2)</math> no pior caso.
==Exemplo de execução==
Repare neste exemplo de execução do algoritmo como as arestas são escolhidas para entrar no subgrafo. O conjunto '''V\U''' são os vértices que ainda não entraram no subgrafo, o conjunto '''U''' são os vértices que já estão no subgrafo, as '''arestas possíveis''' é uma lista de arestas que poderiam ser incluidas no subgrafo, pois conectam vértices contidos no subgrafo com os que ainda não estão e as '''arestas incluídas''' são aquelas que já estão no subgrafo. Dessa maneira e segundo o algoritmo genérico dado acima, para escolhermos uma aresta segura devemos observar o conjunto de arestas possíveis e selecionar aquelas que não formam ciclos com o subgrafo até entao formado e cujo peso é o mínimo possível naquele momento. Se uma aresta apresentar todos estes quesitos podemos considerá-la uma aresta segura.
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! | Imagem
! | Arestas incluídas<BR>no subgrafo
! | U
! | Arestas possíveis
! | V \ U
! | Descrição
|-
|[[Image:Prim Algorithm 0.svg|200px]]
| {} || {} || || {A,B,C,D,E,F,G}
| Este é o grafo original. Os números próximos das arestas significam o seu peso.
|-
|[[Image:Prim Algorithm 1.svg|200px]]
| {DA} ||{D} || {D,A} = 5'''V'''<BR> {D,B}=9 <BR> {D,E}=15 <BR> {D,F}=6 || {A,B,C,E,F,G}
|O vértice '''D''' foi escolhido como ponto inicial do algoritmo. Vértices '''A''', '''B''', '''E''' e '''F''' estão conectados com '''D''' através de uma única aresta. '''A''' é o vértice mais próximo de '''D''' e, portanto a aresta '''AD''' será escolhida para formar o subgrafo.
|-
|[[Image:Prim Algorithm 2.svg|200px]]
| {DA, DF}||{A,D} || {D,B}=9 <BR> {D,E}=15 <BR> {D,F}=6'''V'''<BR> {A,B}=7 || {B,C,E,F,G}
|O próximo vértice escolhido é o mais próximo de '''D''' ou '''A'''. '''B''' está a uma distância 9 de '''D''', '''E''' numa distância 15 e '''F''' numa distância 6. E '''A''' está a uma distância de 7 de '''B'''. Logo devemos escolher a aresta '''DF''', pois é o menor peso.
|-
|[[Image:Prim Algorithm 3.svg|200px]]
| {DA, DF, AB}|| {A,D,F} || {D,B}=9 <BR> {D,E}=15 <BR> {A,B}=7'''V''' <BR> {F,E}=8 <BR> {F,G}=11 || {B,C,E,G}
|Agora devemos escolher o vértice mais próximo dos vértices '''A''', '''D''' ou '''F'''. A aresta em questão é a aresta '''AB'''.
|-
|[[Image:Prim Algorithm 4.svg|200px]]
| {DA, DF, AB, BE} || {A,B,D,F} || {B,C}= 8 <BR> {B,E}=7'''V''' <BR> {D,B}=9'''ciclo'''<BR> {D,E}=15 <BR> {F,E}=8 <BR> {F,G}=11 || {C,E,G}
|Agora podemos escolher entre os vértices '''C''', '''E''', e '''G'''. '''C''' está a uma distância de 8 de '''B''', '''E''' está a uma distância 7 de '''B''' e '''G''' está a 11 de '''F'''. '''E''' é o mais próximo do subgrafo e, portanto escolhemos a aresta '''BE'''.
|-
|[[Image:Prim Algorithm 5.svg|200px]]
| {DA, DF, AB, BE, EC} || {A,B,D,E,F} || {B,C}=8 <BR> {D,B}=9ciclo <BR> {D,E}=15ciclo <BR> {E,C}=5'''V'''<BR>{E,G}=9<BR> {F,E}=8 ciclo<BR>{F,G}=11 || {C,G}
|Restam somente os vértices '''C''' e '''G'''. '''C''' está a uma distância 5 de '''E''' e de '''G''' a '''E''' 9. '''C''' é escolhido, então a aresta '''EC''' entra no subgrafo construído.
|-
|[[Image:Prim Algorithm 6.svg|200px]]
| {DA, DF, AB, BE, EC, EG} ||{A,B,C,D,E,F} || {B,C}=8ciclo<BR>{D,B}=9ciclo<BR>{D,E}=15ciclo<BR>{E,G}=9'''V'''<BR>{F,E}=8ciclo<BR> {F,G}=11 || {G}
|Agora só resta o vértice '''G'''. Ele está a uma distância de 11 de '''F''', e 9 de '''E'''. '''E''' é o mais próximo, então '''G''' entra no subgrafo conectado pela aresta '''EG'''.
|-
|[[Image:Prim Algorithm 7.svg|200px]]
| {DA, DF, AB, BE, EC, EG} ||{A,B,C,D,E,F,G} || {B,C}=8 ciclo<BR>{D,B}=9 ciclo<BR>{D,E}=15 ciclo<BR>{F,E}=8 ciclo<BR>{F,G}=11 ciclo || {}
|Aqui está o fim do algoritmo e o subgrafo formado pelas arestas em verde representam a árvore geradora mínima. Nesse caso esta árvore apresenta a soma de todas as suas arestas o número 39.
|}
==Implementação em PHP==
Linha 117 ⟶ 175:
print_r($v);}
</source>
<!--{{Notas|grupo = "nota"|col=2|refs=
}}-->
{{Referências|col=2|refs=
}}
=={{Bibliografia}}==
*{{Citar livro
|sobrenome= Cormen
|nome= Thomas
|autorlink=
|coautor= Leiserson, Charles
|coautor= Rivest, Ronald
|coautor= Stein, Clifford
|título= Introduction to Algorithms
|subtítulo=
|idioma= inglês
|edição= 2
|local=
|editora= MIT Press and McGraw-Hill
|editor=
|ano= 2001
|páginas=
|volumes=
|página=
|capítulo= 23
|volume=
|coleção=
|isbn= 0-262-03293-7
|ref= cormen
}}
==Ligações Externas==
*[http://www.mincel.com/java/prim.html Algoritmo de Prim]
*[http://students.ceid.upatras.gr/~papagel/project/prim.htm Exemplo animado de um algoritmo de Prim]
*[http://people.csail.mit.edu/rivest/programs.html Demonstração em Python de uma árvore mínima]
*[http://code.google.com/p/annas/ Implementção em Java do algoritmo de Prim]
*[http://code.google.com/p/ngenerics/ Implementação em C# do algoritmo de Prim]
{{esboço-programação}}
| |||