Algoritmo de Prim: diferenças entre revisões

 

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==

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.

 

| Este é o grafo original. Os números próximos das arestas significam o seu peso.

|-

| {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.

|-

| {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.

|-

 

| {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'''.

|-

| {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'''.

|-

| {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.

|-

| {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'''.

|-

| {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.

}}

 

*{{Citar livro

|sobrenome= Cormen

}}

 

*[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]