O algoritmo de Prim é uma abordagem gulosa para encontrar a Árvore Geradora Mínima (MST) de um grafo conectado e ponderado. Diferente do Kruskal, que trabalha com arestas globalmente ordenadas, o Prim cresce a MST a partir de um único vértice, adicionando a cada passo a aresta de menor peso que conecta um vértice já na árvore a um vértice fora dela. Essa estratégia de “crescimento local” é análoga ao funcionamento do Dijkstra, e ambos usam uma fila de prioridade como estrutura central.
O Prim é especialmente eficiente para grafos densos (muitas arestas) quando implementado com lista de adjacência e fila de prioridade. Na prática, é usado nos mesmos cenários que o Kruskal — planejamento de redes de telecomunicações, distribuição de energia elétrica, redes de água e esgoto, e projeto de circuitos — mas brilha quando o grafo tem muitas arestas e queremos evitar o custo de ordená-las todas.
Como Funciona
O algoritmo de Prim segue estes passos:
- Escolhe um vértice inicial arbitrário e o adiciona à MST.
- Para cada aresta que conecta um vértice na MST a um vértice fora dela, insere na fila de prioridade.
- Remove a aresta de menor peso da fila.
- Se o vértice destino ainda não está na MST, adiciona-o e insere suas arestas na fila.
- Repete até que todos os vértices estejam na MST.
Diagrama Visual — Árvore Crescendo
Grafo de exemplo:
(0)---4---(1)
/ \ |
2/ 8\ 6|
/ \ |
(2)---1---(3)---3---(4)
\ /
5\ 7/
\ /
(5)-------(6)
9
Arestas: 0-1:4, 0-2:2, 0-3:8, 1-3:6, 2-3:1, 3-4:3, 2-5:5, 4-6:7, 5-6:9
Execução do Prim a partir do vértice 0:
Passo | Adiciona | Aresta usada | Custo | Fila de prioridade (peso, vértice)
------|----------|-------------|-------|-------------------------------------
0 | 0 | - | 0 | [(2,2), (4,1), (8,3)]
1 | 2 | 0-2 (2) | 2 | [(1,3), (4,1), (5,5), (8,3)]
2 | 3 | 2-3 (1) | 3 | [(3,4), (4,1), (5,5), (6,1)]
3 | 4 | 3-4 (3) | 6 | [(4,1), (5,5), (6,1), (7,6)]
4 | 1 | 0-1 (4) | 10 | [(5,5), (6,3*), (7,6)]
5 | 5 | 2-5 (5) | 15 | [(7,6), (9,6)]
6 | 6 | 4-6 (7) | 22 | [] -> COMPLETO!
MST resultante (custo total = 2+1+3+4+5+7 = 22):
(0)---4---(1)
/
2/
/
(2)---1---(3)---3---(4)
\ \
5\ 7\
\ \
(5) (6)
Representação do Grafo
O Prim trabalha naturalmente com lista de adjacência, pois precisa acessar os vizinhos de cada vértice adicionado à MST.
/// Grafo ponderado representado como lista de adjacência.
/// grafo[u] contém pares (vizinho, peso).
fn criar_grafo(num_vertices: usize) -> Vec<Vec<(usize, u64)>> {
let mut grafo = vec![vec![]; num_vertices];
let arestas = [
(0, 1, 4), (0, 2, 2), (0, 3, 8),
(1, 3, 6), (2, 3, 1), (3, 4, 3),
(2, 5, 5), (4, 6, 7), (5, 6, 9),
];
for (u, v, peso) in arestas {
grafo[u].push((v, peso));
grafo[v].push((u, peso));
}
grafo
}
Complexidade
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor | O((V + E) log V) | O(V + E) |
| Médio | O((V + E) log V) | O(V + E) |
| Pior | O((V + E) log V) | O(V + E) |
Onde V = número de vértices e E = número de arestas.
- Tempo O((V + E) log V): cada vértice é processado uma vez (O(V)), cada aresta é examinada uma vez (O(E)), e cada operação na fila de prioridade custa O(log V).
- Espaço O(V + E): armazena o grafo (O(V + E)), o conjunto de vértices na MST (O(V)) e a fila de prioridade (até O(E) no pior caso por entradas duplicadas).
- Para grafos densos (E perto de V^2), o Prim com matriz de adjacência simples tem O(V^2), melhor que Kruskal O(E log E) = O(V^2 log V).
Implementação em Rust
Prim com BinaryHeap
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashSet};
/// Resultado da MST: arestas selecionadas e custo total.
struct ResultadoMst {
arestas: Vec<(usize, usize, u64)>, // (u, v, peso)
custo_total: u64,
}
/// Executa o algoritmo de Prim a partir do vértice `inicio`.
/// Retorna None se o grafo não é conexo.
fn prim(
grafo: &Vec<Vec<(usize, u64)>>,
inicio: usize,
) -> Option<ResultadoMst> {
let n = grafo.len();
let mut na_mst = HashSet::new();
let mut heap = BinaryHeap::new();
let mut arestas_mst = Vec::new();
let mut custo_total: u64 = 0;
// Adiciona o vértice inicial à MST
na_mst.insert(inicio);
// Enfileira todas as arestas do vértice inicial
for &(vizinho, peso) in &grafo[inicio] {
// (peso, destino, origem) — Reverse para min-heap
heap.push(Reverse((peso, vizinho, inicio)));
}
while let Some(Reverse((peso, v, u))) = heap.pop() {
// Se o vértice já está na MST, ignora
if na_mst.contains(&v) {
continue;
}
// Adiciona o vértice e a aresta à MST
na_mst.insert(v);
arestas_mst.push((u, v, peso));
custo_total += peso;
// Enfileira arestas do novo vértice
for &(vizinho, peso_aresta) in &grafo[v] {
if !na_mst.contains(&vizinho) {
heap.push(Reverse((peso_aresta, vizinho, v)));
}
}
}
if na_mst.len() == n {
Some(ResultadoMst {
arestas: arestas_mst,
custo_total,
})
} else {
None // Grafo desconexo
}
}
fn main() {
let mut grafo = vec![vec![]; 7];
let arestas = [
(0, 1, 4), (0, 2, 2), (0, 3, 8),
(1, 3, 6), (2, 3, 1), (3, 4, 3),
(2, 5, 5), (4, 6, 7), (5, 6, 9),
];
for (u, v, peso) in arestas {
grafo[u].push((v, peso));
grafo[v].push((u, peso));
}
match prim(&grafo, 0) {
Some(resultado) => {
println!("Arestas da Árvore Geradora Mínima:");
for (u, v, peso) in &resultado.arestas {
println!(" {} -- {} (peso {})", u, v, peso);
}
println!("Custo total: {}", resultado.custo_total);
}
None => println!("Grafo não é conexo!"),
}
// Saída:
// Arestas da Árvore Geradora Mínima:
// 0 -- 2 (peso 2)
// 2 -- 3 (peso 1)
// 3 -- 4 (peso 3)
// 0 -- 1 (peso 4)
// 2 -- 5 (peso 5)
// 4 -- 6 (peso 7)
// Custo total: 22
}
Prim com Rastreamento de Custos Mínimos
Esta versão rastreia o menor custo para adicionar cada vértice à MST, similar ao Dijkstra.
use std::cmp::Reverse;
use std::collections::BinaryHeap;
/// Prim com vetor de custos mínimos (mais eficiente para grafos densos).
fn prim_com_custos(grafo: &Vec<Vec<(usize, u64)>>) -> Option<u64> {
let n = grafo.len();
if n == 0 {
return Some(0);
}
let mut custo_minimo = vec![u64::MAX; n]; // Custo mínimo para entrar na MST
let mut na_mst = vec![false; n];
let mut heap = BinaryHeap::new();
let mut custo_total: u64 = 0;
let mut vertices_na_mst = 0;
// Começa pelo vértice 0
custo_minimo[0] = 0;
heap.push(Reverse((0u64, 0usize)));
while let Some(Reverse((custo, v))) = heap.pop() {
if na_mst[v] {
continue;
}
na_mst[v] = true;
custo_total += custo;
vertices_na_mst += 1;
for &(vizinho, peso) in &grafo[v] {
if !na_mst[vizinho] && peso < custo_minimo[vizinho] {
custo_minimo[vizinho] = peso;
heap.push(Reverse((peso, vizinho)));
}
}
}
if vertices_na_mst == n {
Some(custo_total)
} else {
None
}
}
fn main() {
let mut grafo = vec![vec![]; 7];
let arestas = [
(0, 1, 4), (0, 2, 2), (0, 3, 8),
(1, 3, 6), (2, 3, 1), (3, 4, 3),
(2, 5, 5), (4, 6, 7), (5, 6, 9),
];
for (u, v, peso) in arestas {
grafo[u].push((v, peso));
grafo[v].push((u, peso));
}
match prim_com_custos(&grafo) {
Some(custo) => println!("Custo total da MST: {}", custo),
None => println!("Grafo não é conexo!"),
}
// Saída: Custo total da MST: 22
}
Prim com HashMap para Vértices Nomeados
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet};
/// Prim para grafos com vértices nomeados (strings).
fn prim_nomeado(
grafo: &HashMap<&str, Vec<(&str, u64)>>,
inicio: &str,
) -> Option<(Vec<(&str, &str, u64)>, u64)> {
let n = grafo.len();
let mut na_mst = HashSet::new();
let mut heap = BinaryHeap::new();
let mut arestas_mst = Vec::new();
let mut custo_total: u64 = 0;
na_mst.insert(inicio);
if let Some(vizinhos) = grafo.get(inicio) {
for &(vizinho, peso) in vizinhos {
heap.push(Reverse((peso, vizinho, inicio)));
}
}
while let Some(Reverse((peso, v, u))) = heap.pop() {
if na_mst.contains(v) {
continue;
}
na_mst.insert(v);
arestas_mst.push((u, v, peso));
custo_total += peso;
if let Some(vizinhos) = grafo.get(v) {
for &(vizinho, peso_aresta) in vizinhos {
if !na_mst.contains(vizinho) {
heap.push(Reverse((peso_aresta, vizinho, v)));
}
}
}
}
if na_mst.len() == n {
Some((arestas_mst, custo_total))
} else {
None
}
}
fn main() {
let mut grafo: HashMap<&str, Vec<(&str, u64)>> = HashMap::new();
// Rede de cidades
grafo.insert("SP", vec![("RJ", 400), ("BH", 580), ("Campinas", 100)]);
grafo.insert("RJ", vec![("SP", 400), ("BH", 440), ("Vitória", 520)]);
grafo.insert("BH", vec![("SP", 580), ("RJ", 440), ("Vitória", 520)]);
grafo.insert("Campinas", vec![("SP", 100), ("Vitória", 900)]);
grafo.insert("Vitória", vec![("RJ", 520), ("BH", 520), ("Campinas", 900)]);
match prim_nomeado(&grafo, "SP") {
Some((arestas, custo)) => {
println!("Rede de menor custo:");
for (u, v, peso) in &arestas {
println!(" {} -- {} ({} km)", u, v, peso);
}
println!("Distância total: {} km", custo);
}
None => println!("Não é possível conectar todas as cidades."),
}
// Saída:
// Rede de menor custo:
// SP -- Campinas (100 km)
// SP -- RJ (400 km)
// RJ -- BH (440 km)
// RJ -- Vitória (520 km)
// Distância total: 1460 km
}
Exemplo de Execução
Projeto de rede elétrica conectando 5 bairros:
Bairros: Centro(0), Norte(1), Sul(2), Leste(3), Oeste(4)
Custos de instalação (milhares de R$):
Centro-Norte: 12 Centro-Sul: 8 Centro-Leste: 15
Centro-Oeste: 10 Norte-Leste: 7 Sul-Oeste: 6
Sul-Leste: 9 Leste-Oeste: 11
Prim a partir de Centro(0):
Passo 0: MST={Centro}, Fila=[(8,Sul,Centro), (10,Oeste,Centro),
(12,Norte,Centro), (15,Leste,Centro)]
Passo 1: Remove (8,Sul,Centro)
MST={Centro, Sul}, adiciona aresta Centro-Sul(8)
Adiciona: (6,Oeste,Sul), (9,Leste,Sul)
Passo 2: Remove (6,Oeste,Sul)
MST={Centro, Sul, Oeste}, adiciona aresta Sul-Oeste(6)
Adiciona: (11,Leste,Oeste)
Passo 3: Remove (9,Leste,Sul)
MST={Centro, Sul, Oeste, Leste}, adiciona aresta Sul-Leste(9)
Adiciona: (7,Norte,Leste)
Passo 4: Remove (7,Norte,Leste)
MST={Centro, Sul, Oeste, Leste, Norte}, adiciona aresta Leste-Norte(7)
-> COMPLETO!
MST: Centro-Sul(8), Sul-Oeste(6), Sul-Leste(9), Leste-Norte(7)
Custo total: 30 mil R$
Variações e Otimizações
1. Prim Lazy vs Eager
A implementação acima é “lazy” — insere todas as arestas na fila e ignora as obsoletas. A versão “eager” usa um decrease_key para atualizar prioridades na fila, evitando entradas duplicadas. O BinaryHeap de Rust não suporta decrease_key nativamente, mas a abordagem lazy funciona bem na prática.
2. Prim com Matriz de Adjacência
Para grafos densos (E perto de V^2), uma implementação O(V^2) simples com matriz de adjacência pode ser mais rápida que a versão com heap, eliminando o overhead logarítmico.
3. MST Incremental
Se o grafo muda incrementalmente (arestas adicionadas/removidas), o Prim pode ser adaptado para atualizar a MST sem recalcular do zero.
Quando Usar
Use Prim quando:
- Precisa da árvore geradora mínima de um grafo.
- O grafo é denso (muitas arestas em relação aos vértices).
- O grafo é representado como lista de adjacência (ou matriz de adjacência).
- Quer uma abordagem de crescimento local (cresce a árvore a partir de um ponto).
- Precisa processar o grafo de forma streaming (vértices adicionados incrementalmente).
Evite Prim quando:
- O grafo é esparso — Kruskal com Union-Find pode ser mais simples e eficiente.
- As arestas já estão pré-ordenadas — Kruskal aproveita isso diretamente.
- O grafo é desconexo — Kruskal lida com isso naturalmente.
Comparação com Outros Algoritmos
| Característica | Prim | Kruskal | Dijkstra |
|---|---|---|---|
| Problema resolvido | MST | MST | Caminho mínimo |
| Abordagem | Cresce árvore (local) | Seleciona arestas (global) | Cresce árvore (local) |
| Estrutura auxiliar | Fila de prioridade | Union-Find | Fila de prioridade |
| Complexidade (heap) | O((V+E) log V) | O(E log E) | O((V+E) log V) |
| Grafos densos | Excelente | Ruim | Bom |
| Grafos esparsos | Bom | Excelente | Bom |
| Grafos desconexos | Precisa adaptar | Floresta automática | N/A |
| Vértice inicial importa? | Nao (MST é a mesma) | N/A | Sim (fonte única) |
Exercícios Práticos
Rede de água: Dadas N casas e M possíveis tubulações com custos, encontre o custo mínimo para fornecer água a todas as casas. Uma casa já tem acesso direto à rede pública (vértice inicial).
Prim vs Kruskal: Implemente ambos os algoritmos para o mesmo grafo e verifique que produzem MSTs com o mesmo custo total (as arestas podem diferir em caso de empate de pesos).
MST com aresta obrigatória: Modifique o Prim para garantir que uma aresta específica faça parte da MST. Dica: comece a execução pelos dois vértices dessa aresta.
Árvore geradora de segundo menor custo: Use o Prim para encontrar a MST, depois encontre a árvore geradora com o segundo menor custo total trocando exatamente uma aresta.
Veja Também
BinaryHeap— Fila de prioridade — estrutura central do algoritmo de PrimHashMap— Mapa hash — para grafos com vértices nomeadosHashSet— Conjunto hash — para rastrear vértices na MSTVec— Vetor dinâmico — para lista de adjacência- Algoritmo de Kruskal — alternativa com Union-Find para MST
- Algoritmo de Dijkstra — algoritmo similar usado para caminho mínimo