Ideia de implementação
O algoritmo de Prim pode ser implementado de diferentes formas, mas a ideia central é sempre a mesma: manter o controle da aresta mais barata que conecta cada vértice externo à árvore atual.
Em vez de inspecionar todo o grafo manualmente a cada passo, normalmente utilizamos uma fila de prioridade ordenada pelo custo mínimo de conexão.
Estruturas de dados
Uma implementação comum utiliza:
- key[v]: menor custo conhecido para conectar o vértice v à árvore;
- parent[v]: vértice que conecta v à árvore geradora mínima;
- visited[v]: indica se v já está na árvore;
- fila de prioridade: armazena os vértices ordenados pelo valor de key.
Ao final, o vetor parent descreve a árvore geradora mínima.
Pseudocódigo
Prim(G, inicio):
para cada vértice v em G:
key[v] = infinito
parent[v] = nulo
visited[v] = falso
key[inicio] = 0
filaPrioridade.insert(inicio, 0)
enquanto filaPrioridade não está vazia:
u = filaPrioridade.extractMin()
se visited[u]:
continue
visited[u] = verdadeiro
para cada aresta (u, v) com peso w:
se not visited[v] e w < key[v]:
key[v] = w
parent[v] = u
filaPrioridade.insert(v, key[v])
retornar parentO algoritmo escolhe repetidamente o próximo vértice com menor custo e atualiza as melhores conexões para seus vizinhos.
Como interpretar o pseudocódigo
O valor key[v] representa a melhor aresta encontrada até o momento para conectar o vértice v à árvore.
Quando encontramos uma aresta melhor, atualizamos key[v] e parent[v].
A fila de prioridade garante que o próximo vértice escolhido seja sempre o de menor custo.
parent[v] indica qual aresta conecta v.
Complexidade
A complexidade do algoritmo de Prim depende da representação do grafo e da estrutura usada para escolher a próxima aresta mínima.
| Implementação | Uso típico | Complexidade |
|---|---|---|
| Matriz de adjacência | Grafos densos | O(V²) |
| Lista de adjacência + heap binário | Grafos esparsos | O((V + E) log V) |
| Lista de adjacência + heap de Fibonacci | Otimização teórica | O(E + V log V) |
Na prática, lista de adjacência com heap binário é a escolha mais comum.
O que são V e E?
Em algoritmos de grafos:
- V: número de vértices;
- E: número de arestas.
Grafos densos possuem muitas arestas. Grafos esparsos possuem relativamente poucas.
Prim vs Kruskal na prática
Ambos encontram árvores geradoras mínimas, mas com estratégias diferentes.
| Prim | Kruskal |
|---|---|
| Constrói uma única árvore | Une componentes |
| Usa fila de prioridade | Usa Union-Find |
| Foca na fronteira da árvore | Foca nas arestas ordenadas |
| Bom para grafos densos | Bom para grafos esparsos |
Erros comuns
- Escolher a menor aresta global em vez da menor que sai da árvore.
- Conectar vértices já presentes na árvore.
- Esquecer que o grafo precisa ser conexo.
- Confundir arestas analisadas com as da solução final.
Resumo final
O algoritmo de Prim é um algoritmo guloso para encontrar uma árvore geradora mínima em grafos ponderados e conexos.
Ele começa de um vértice e cresce uma única árvore, sempre adicionando a menor aresta que conecta a um novo vértice.
Sua correção vem da propriedade do corte, e sua eficiência depende das estruturas utilizadas.
Próximo passo
Depois de Prim e Kruskal, o próximo passo natural é estudar caminhos mínimos.
Enquanto árvores geradoras mínimas minimizam o custo total, algoritmos como Dijkstra minimizam caminhos individuais.
Apesar de parecidos, são problemas diferentes.