Algoritmo de Prim

Imagine que está a instalar cabo a partir de uma central elétrica: liga primeiro a cidade mais próxima, depois a cidade mais próxima de qualquer ponto já ligado, e assim por diante. Isso é o algoritmo de Prim, e termina sempre com a rede mais barata possível.

Um grafo com uma árvore a crescer a partir de um nó, os nós em espera à volta com as suas melhores arestas tracejadas, e por baixo a lista dos nós em espera
Um grafo com uma árvore a crescer a partir de um nó, os nós em espera à volta com as suas melhores arestas tracejadas, e por baixo a lista dos nós em espera

A ideia

Uma árvore de extensão mínima liga todos os nós de um grafo ponderado com o menor comprimento total de arestas possível. O algoritmo de Prim constrói-a fazendo crescer uma só árvore para fora a partir de uma origem. A árvore nunca se divide em partes: em cada passo entra exatamente um nó novo, pela aresta mais curta que sai da árvore.

Passo a passo

Ponha a origem na árvore. Para cada nó fora da árvore, guarde a sua melhor aresta: a sua aresta mais curta até qualquer nó da árvore. Depois repita: escolha o nó de fora cuja melhor aresta é a mais curta, junte-o à árvore com essa aresta e verifique as suas arestas. Um vizinho fora da árvore que agora pode ser alcançado por uma aresta mais curta fica com essa aresta como a sua nova melhor. Pare quando todos os nós estiverem na árvore.

Um exemplo

Tome as arestas A–B de comprimento 1, B–C 2, A–C 3, C–D 4 e B–D 5, e comece em A. As arestas de A dão a B a melhor aresta 1 e a C a melhor aresta 3. B é o mais próximo, por isso entra por A–B; as suas arestas melhoram C para 2 e dão 5 a D. C entra por B–C, e a sua aresta C–D melhora D para 4. Por fim, D entra por C–D. A árvore A–B, B–C, C–D tem comprimento total 1 + 2 + 4 = 7.

Porque é que está correto

Em cada passo, os nós estão divididos em dois grupos: os que estão na árvore e os que estão fora. A propriedade do corte diz que a aresta mais curta entre dois grupos assim pertence sempre a alguma árvore de extensão mínima. Prim junta sempre exatamente essa aresta, por isso a árvore construída até agora pode sempre ser completada até uma árvore de extensão mínima, e quando todos os nós tiverem entrado, é uma.

História e velocidade

O matemático checo Vojtěch Jarník publicou o algoritmo em 1930. Robert Prim redescobriu-o nos Bell Labs em 1957, e Edsger Dijkstra outra vez em 1959. Com os nós em espera num heap binário, o trabalho cresce com E log V para V nós e E arestas; com um simples array é cerca de V², o que é melhor quando quase todos os pares de nós estão ligados. Com um heap de Fibonacci é E + V log V.

Experimente

Abra a aplicação, clique num nó para começar aí e prima Avançar. Os nós na árvore são verdes, os nós em espera azuis, e a melhor aresta de cada nó em espera é desenhada tracejada. Os nós em espera aparecem por baixo do grafo com o comprimento da sua melhor aresta, da mais curta para a mais longa: o primeiro é o próximo a entrar. Comece em nós diferentes e veja a ordem mudar enquanto o total fica igual.

Perguntas frequentes

Qual é a diferença entre o algoritmo de Prim e o de Dijkstra?

Ambos fazem crescer uma região a partir de uma origem com uma fila de prioridade. Prim ordena um nó em espera pelo comprimento da sua melhor aresta até à árvore; Dijkstra pela sua distância completa desde a origem. Prim dá uma árvore de extensão mínima, Dijkstra uma árvore de caminhos mais curtos.

O algoritmo de Prim funciona com comprimentos de aresta negativos?

Sim. Ao contrário do algoritmo de Dijkstra, Prim só compara arestas entre si, por isso os comprimentos negativos não causam problemas: continua a encontrar uma árvore de extensão com o menor total.

E se o grafo não for conexo?

Então o algoritmo de Prim para assim que tiver alcançado todos os nós que consegue: dá uma árvore de extensão mínima apenas da parte que contém a origem. Executá-lo de novo a partir de um nó ainda não alcançado dá uma floresta de extensão mínima.

O algoritmo de Prim ou o de Kruskal: qual é melhor?

Nenhum ganha sempre. Prim adequa-se a grafos densos e a grafos guardados como listas de vizinhos; Kruskal a grafos esparsos dados como lista de arestas. Ambos encontram uma árvore com o mesmo comprimento total.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar o algoritmo de Prim