Algoritmo de Prim
Na ciência da computação o algoritmo de Prim é um algoritmo guloso empregado para encontrar uma árvore geradora mínima 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.
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:
π[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.
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 | l o g | V | ) {\displaystyle O(|A|log|V|)} e O ( V 2 ) {\displaystyle O(V^{2})} no pior caso.
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.
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 | l o g | V | ) {\displaystyle O(|V|+|A|log|V|)} . Uma função adicional, primDesconexo, resolve o problema para grafos desconexos, sem alterar a complexidade de tempo do algoritmo.
