# Algoritmo de Prim

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 árvores geradoras mínimas são o algoritmo de Kruskal e algoritmo de Boruvka, sendo que este último pode ser empregado em grafos desconexos, enquanto o algoritmo de Prim e o Algoritmo de Kruskal precisam de um grafo conexo.

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

### 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 houver vértices que não estão no subgrafo
          selecione uma aresta segura
          insira a aresta segura e seu vértice no subgrafo

## Pseudocódigo

π[v] indica o predecessor de v. Após o término do algoritmo, para cada v pertencente aos vértices de G, π[v]→v representa uma aresta selecionada para a árvore geradora mínima se π[v] ≠ nulo. O algoritmo retorna o conjunto dessas arestas, formado pelos pares (π[v], v). Q é um conjunto de pares (peso, vértice). O método extrair-mín(Q) deve extrair o menor elemento de Q; um par (a,b) é menor que um par (c,d) se a < c ou se a = c e b < d. S é um conjunto que armazena os vértices cujas adjacências já foram analisadas.

## 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 listas de adjacência e por matrizes de adjacência e suas respectivas complexidades $O(|A|log|V|)$ e $O(V^{2})$ 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é então formado e cujo peso é o mínimo possível naquele momento. Se uma aresta apresentar todos estes quesitos podemos considerá-la uma aresta segura.
| Arestas incluídas no subgrafo | U | Arestas possíveis | V \ U | Descrição |
| | | | {A,B,C,D,E,F,G} | Este é o grafo original. Os números próximos das arestas significam o seu peso. |
| {DA} | {D} | {D,A} = 5V {D,B}=9 {D,E}=15 {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 {D,E}=15 {D,F}=6V {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 {D,E}=15 {A,B}=7V {F,E}=8 {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 {B,E}=7V {D,B}=9ciclo {D,E}=15 {F,E}=8 {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 {D,B}=9ciclo {D,E}=15ciclo {E,C}=5V {E,G}=9 {F,E}=8 ciclo {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 {D,B}=9ciclo {D,E}=15ciclo {E,G}=9V {F,E}=8ciclo {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 {D,B}=9 ciclo {D,E}=15 ciclo {F,E}=8 ciclo {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ções
### Implementação em Python

A implementação a seguir usa uma lista de adjacência para representar o grafo. A complexidade de tempo é $O(|V|+|A|log|V|)$. Uma função adicional, primDesconexo, resolve o problema para grafos desconexos, sem alterar a complexidade de tempo do algoritmo.