O algoritmo de Kruskal encontra a Árvore Geradora Mínima (Minimum Spanning Tree, ou MST) de um grafo conectado e ponderado. A MST é um subconjunto de arestas que conecta todos os vértices do grafo com o menor custo total possível, sem formar ciclos. Kruskal utiliza uma abordagem gulosa: ordena todas as arestas por peso e as adiciona uma a uma, desde que não formem ciclo, usando a estrutura de dados Union-Find (Disjoint Set Union) para verificar conectividade de forma eficiente.
Na prática, a MST é fundamental em projetos de infraestrutura: planejar a rede de cabos de fibra óptica de menor custo, projetar circuitos elétricos, planejar redes de estradas ou tubulações, e em algoritmos de clustering e segmentação de imagens. O Kruskal é especialmente eficiente para grafos esparsos (poucos arestas em relação ao número de vértices).
Como Funciona
O algoritmo de Kruskal segue estes passos:
- Ordena todas as arestas do grafo por peso (menor para maior).
- Inicializa uma estrutura Union-Find com cada vértice em seu próprio conjunto.
- Para cada aresta (em ordem crescente de peso):
- Se os dois vértices da aresta estão em conjuntos diferentes, adiciona a aresta à MST e une os conjuntos.
- Se já estão no mesmo conjunto, pula (adicioná-la criaria um ciclo).
- Para quando a MST tem V-1 arestas (ou quando todas as arestas foram processadas).
Diagrama Visual — Seleção de Arestas
Grafo de exemplo:
(0)---4---(1)
/ \ |
8/ 2\ 6|
/ \ |
(3)---1---(2)---3---(4)
\ / /
7\ 5/ 9/
\ / /
(5)---10---(6)
Arestas ordenadas por peso:
Peso | Aresta | Ação | Union-Find (conjuntos)
-----|--------|--------------------|---------------------------------
1 | 2-3 | Adiciona (MST) | {0} {1} {2,3} {4} {5} {6}
2 | 0-2 | Adiciona (MST) | {0,2,3} {1} {4} {5} {6}
3 | 2-4 | Adiciona (MST) | {0,2,3,4} {1} {5} {6}
4 | 0-1 | Adiciona (MST) | {0,1,2,3,4} {5} {6}
5 | 2-5 | Adiciona (MST) | {0,1,2,3,4,5} {6}
6 | 1-2 | REJEITA (ciclo) | 1 e 2 já no mesmo conjunto
7 | 3-5 | REJEITA (ciclo) | 3 e 5 já no mesmo conjunto
8 | 0-3 | REJEITA (ciclo) | 0 e 3 já no mesmo conjunto
9 | 4-6 | Adiciona (MST) | {0,1,2,3,4,5,6} -> COMPLETO!
MST resultante (6 arestas, peso total = 1+2+3+4+5+9 = 24):
(0)---4---(1)
\
2\
\
(3)---1---(2)---3---(4)
/ \
5/ 9\
/ \
(5) (6)
Representação do Grafo
Para Kruskal, a representação mais natural é uma lista de arestas, já que o algoritmo itera sobre as arestas ordenadas.
/// Uma aresta com peso.
#[derive(Clone, Debug)]
struct Aresta {
u: usize,
v: usize,
peso: u64,
}
/// Cria a lista de arestas do grafo.
fn criar_arestas() -> Vec<Aresta> {
vec![
Aresta { u: 0, v: 1, peso: 4 },
Aresta { u: 0, v: 2, peso: 2 },
Aresta { u: 0, v: 3, peso: 8 },
Aresta { u: 1, v: 2, peso: 6 },
Aresta { u: 2, v: 3, peso: 1 },
Aresta { u: 2, v: 4, peso: 3 },
Aresta { u: 2, v: 5, peso: 5 },
Aresta { u: 3, v: 5, peso: 7 },
Aresta { u: 4, v: 6, peso: 9 },
Aresta { u: 5, v: 6, peso: 10 },
]
}
Complexidade
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor | O(E log E) | O(V + E) |
| Médio | O(E log E) | O(V + E) |
| Pior | O(E log E) | O(V + E) |
Onde V = número de vértices e E = número de arestas.
- Tempo O(E log E): dominado pela ordenação das arestas. As operações de Union-Find com compressão de caminho e união por rank são quase O(1) amortizado (O(alfa(V)), onde alfa é a função inversa de Ackermann, praticamente constante).
- Espaço O(V + E): armazena a lista de arestas (O(E)) e a estrutura Union-Find (O(V)).
- Como E pode ser no máximo V^2, temos O(E log E) = O(E log V^2) = O(2E log V) = O(E log V).
Implementação em Rust
Union-Find (Disjoint Set Union)
/// Estrutura Union-Find com compressão de caminho e união por rank.
struct UnionFind {
pai: Vec<usize>,
rank: Vec<usize>,
}
impl UnionFind {
/// Cria Union-Find com `n` elementos, cada um em seu próprio conjunto.
fn new(n: usize) -> Self {
UnionFind {
pai: (0..n).collect(), // Cada elemento é seu próprio pai
rank: vec![0; n],
}
}
/// Encontra o representante (raiz) do conjunto que contém `x`.
/// Usa compressão de caminho para otimizar buscas futuras.
fn find(&mut self, x: usize) -> usize {
if self.pai[x] != x {
self.pai[x] = self.find(self.pai[x]); // Compressão de caminho
}
self.pai[x]
}
/// Une os conjuntos que contêm `x` e `y`.
/// Retorna true se estavam em conjuntos diferentes (união realizada).
fn union(&mut self, x: usize, y: usize) -> bool {
let raiz_x = self.find(x);
let raiz_y = self.find(y);
if raiz_x == raiz_y {
return false; // Já estão no mesmo conjunto
}
// União por rank: árvore menor é anexada à maior
match self.rank[raiz_x].cmp(&self.rank[raiz_y]) {
std::cmp::Ordering::Less => self.pai[raiz_x] = raiz_y,
std::cmp::Ordering::Greater => self.pai[raiz_y] = raiz_x,
std::cmp::Ordering::Equal => {
self.pai[raiz_y] = raiz_x;
self.rank[raiz_x] += 1;
}
}
true
}
}
Kruskal Completo
#[derive(Clone, Debug)]
struct Aresta {
u: usize,
v: usize,
peso: u64,
}
struct UnionFind {
pai: Vec<usize>,
rank: Vec<usize>,
}
impl UnionFind {
fn new(n: usize) -> Self {
UnionFind {
pai: (0..n).collect(),
rank: vec![0; n],
}
}
fn find(&mut self, x: usize) -> usize {
if self.pai[x] != x {
self.pai[x] = self.find(self.pai[x]);
}
self.pai[x]
}
fn union(&mut self, x: usize, y: usize) -> bool {
let raiz_x = self.find(x);
let raiz_y = self.find(y);
if raiz_x == raiz_y {
return false;
}
match self.rank[raiz_x].cmp(&self.rank[raiz_y]) {
std::cmp::Ordering::Less => self.pai[raiz_x] = raiz_y,
std::cmp::Ordering::Greater => self.pai[raiz_y] = raiz_x,
std::cmp::Ordering::Equal => {
self.pai[raiz_y] = raiz_x;
self.rank[raiz_x] += 1;
}
}
true
}
}
/// Executa o algoritmo de Kruskal.
/// Retorna as arestas da MST e o custo total.
fn kruskal(num_vertices: usize, arestas: &mut Vec<Aresta>) -> (Vec<Aresta>, u64) {
// Passo 1: Ordena arestas por peso
arestas.sort_by_key(|a| a.peso);
// Passo 2: Inicializa Union-Find
let mut uf = UnionFind::new(num_vertices);
let mut mst = Vec::new();
let mut custo_total: u64 = 0;
// Passo 3: Processa arestas em ordem crescente de peso
for aresta in arestas.iter() {
if uf.union(aresta.u, aresta.v) {
custo_total += aresta.peso;
mst.push(aresta.clone());
// MST completa tem V-1 arestas
if mst.len() == num_vertices - 1 {
break;
}
}
}
(mst, custo_total)
}
fn main() {
let mut arestas = vec![
Aresta { u: 0, v: 1, peso: 4 },
Aresta { u: 0, v: 2, peso: 2 },
Aresta { u: 0, v: 3, peso: 8 },
Aresta { u: 1, v: 2, peso: 6 },
Aresta { u: 2, v: 3, peso: 1 },
Aresta { u: 2, v: 4, peso: 3 },
Aresta { u: 2, v: 5, peso: 5 },
Aresta { u: 3, v: 5, peso: 7 },
Aresta { u: 4, v: 6, peso: 9 },
Aresta { u: 5, v: 6, peso: 10 },
];
let (mst, custo) = kruskal(7, &mut arestas);
println!("Arestas da Árvore Geradora Mínima:");
for aresta in &mst {
println!(" {} -- {} (peso {})", aresta.u, aresta.v, aresta.peso);
}
println!("Custo total: {}", custo);
// Saída:
// Arestas da Árvore Geradora Mínima:
// 2 -- 3 (peso 1)
// 0 -- 2 (peso 2)
// 2 -- 4 (peso 3)
// 0 -- 1 (peso 4)
// 2 -- 5 (peso 5)
// 4 -- 6 (peso 9)
// Custo total: 24
}
Verificação de Grafo Conexo
#[derive(Clone, Debug)]
struct Aresta {
u: usize,
v: usize,
peso: u64,
}
struct UnionFind {
pai: Vec<usize>,
rank: Vec<usize>,
num_componentes: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
UnionFind {
pai: (0..n).collect(),
rank: vec![0; n],
num_componentes: n,
}
}
fn find(&mut self, x: usize) -> usize {
if self.pai[x] != x {
self.pai[x] = self.find(self.pai[x]);
}
self.pai[x]
}
fn union(&mut self, x: usize, y: usize) -> bool {
let raiz_x = self.find(x);
let raiz_y = self.find(y);
if raiz_x == raiz_y {
return false;
}
match self.rank[raiz_x].cmp(&self.rank[raiz_y]) {
std::cmp::Ordering::Less => self.pai[raiz_x] = raiz_y,
std::cmp::Ordering::Greater => self.pai[raiz_y] = raiz_x,
std::cmp::Ordering::Equal => {
self.pai[raiz_y] = raiz_x;
self.rank[raiz_x] += 1;
}
}
self.num_componentes -= 1;
true
}
fn componentes(&self) -> usize {
self.num_componentes
}
}
/// Kruskal com verificação de conectividade.
/// Retorna None se o grafo não é conexo.
fn kruskal_seguro(
num_vertices: usize,
arestas: &mut Vec<Aresta>,
) -> Option<(Vec<Aresta>, u64)> {
arestas.sort_by_key(|a| a.peso);
let mut uf = UnionFind::new(num_vertices);
let mut mst = Vec::new();
let mut custo_total: u64 = 0;
for aresta in arestas.iter() {
if uf.union(aresta.u, aresta.v) {
custo_total += aresta.peso;
mst.push(aresta.clone());
if mst.len() == num_vertices - 1 {
break;
}
}
}
if uf.componentes() == 1 {
Some((mst, custo_total))
} else {
None // Grafo desconexo
}
}
fn main() {
// Grafo desconexo: vértice 4 isolado
let mut arestas = vec![
Aresta { u: 0, v: 1, peso: 3 },
Aresta { u: 0, v: 2, peso: 5 },
Aresta { u: 1, v: 2, peso: 1 },
Aresta { u: 3, v: 2, peso: 4 },
// Vértice 4 não tem arestas
];
match kruskal_seguro(5, &mut arestas) {
Some((mst, custo)) => {
println!("MST encontrada com custo {}", custo);
for a in &mst {
println!(" {} -- {} (peso {})", a.u, a.v, a.peso);
}
}
None => println!("Grafo não é conexo! MST não existe."),
}
// Saída: Grafo não é conexo! MST não existe.
}
Exemplo de Execução
Problema: conectar 5 cidades com fibra óptica ao menor custo.
Cidades: A(0), B(1), C(2), D(3), E(4)
Custos de conexão (em milhares de reais):
A-B: 10, A-C: 20, A-D: 30
B-C: 5, B-D: 15, B-E: 25
C-D: 8, C-E: 12
D-E: 18
Arestas ordenadas: B-C(5), C-D(8), A-B(10), C-E(12), B-D(15), D-E(18), A-C(20), B-E(25), A-D(30)
Passo 1: B-C (5) -> Adiciona. Conjuntos: {A} {B,C} {D} {E}
Passo 2: C-D (8) -> Adiciona. Conjuntos: {A} {B,C,D} {E}
Passo 3: A-B (10) -> Adiciona. Conjuntos: {A,B,C,D} {E}
Passo 4: C-E (12) -> Adiciona. Conjuntos: {A,B,C,D,E} -> COMPLETO!
MST: B-C(5), C-D(8), A-B(10), C-E(12)
Custo total: 35 mil reais
(A)---10---(B)
|
5|
|
(D)---8---(C)---12---(E)
Variações e Otimizações
1. Kruskal para Árvore Geradora Máxima
Inverta a ordenação (ordene por peso decrescente) para encontrar a árvore geradora máxima. Útil em problemas onde você quer maximizar o custo mínimo de uma aresta no caminho entre quaisquer dois vértices.
2. Floresta Geradora Mínima
Se o grafo é desconexo, o Kruskal encontra automaticamente uma floresta geradora mínima — uma MST para cada componente conexo.
3. Kruskal com Restrições
Em cenários reais, algumas arestas podem ser obrigatórias ou proibidas. Adicione as arestas obrigatórias primeiro (fazendo union dos seus vértices) e depois execute o Kruskal normalmente no restante.
Quando Usar
Use Kruskal quando:
- Precisa da árvore geradora mínima de um grafo.
- O grafo é esparso (E bem menor que V^2).
- As arestas já estão disponíveis como lista (fácil de ordenar).
- Precisa de uma implementação simples e direta.
- Quer identificar componentes conexos como efeito colateral.
Evite Kruskal quando:
- O grafo é denso (E perto de V^2) — Prim com fila de prioridade pode ser melhor.
- Precisa da MST de forma incremental (adicionando vértices um a um) — Prim é mais natural.
Comparação com Outros Algoritmos
| Característica | Kruskal | Prim | Boruvka |
|---|---|---|---|
| Abordagem | Arestas (global) | Vértices (local) | Componentes |
| Estrutura auxiliar | Union-Find | Fila de prioridade | Union-Find |
| Complexidade | O(E log E) | O((V+E) log V) | O(E log V) |
| Melhor para grafos | Esparsos | Densos | Paralelos |
| Ordenação necessária | Sim (arestas) | Nao | Nao |
| Grafos desconexos | Encontra floresta | Precisa adaptar | Encontra floresta |
| Simplicidade | Alta | Média | Média |
Exercícios Práticos
Rede de fibra óptica: Dadas N cidades e M possíveis conexões com custos, encontre o custo mínimo para conectar todas as cidades. Se não for possível conectar todas, informe quantos componentes desconexos restam.
Segunda menor MST: Encontre a segunda árvore geradora mínima (MST com o segundo menor custo). Dica: para cada aresta da MST, tente substituí-la pela melhor aresta fora da MST.
Kruskal reverso: Implemente o algoritmo de Kruskal “ao contrário”: comece com todas as arestas e vá removendo a de maior peso, desde que o grafo continue conexo.
Custo mínimo de gargalo: Encontre a árvore geradora onde a aresta de maior peso seja a menor possível (minimax path tree). Dica: a MST de Kruskal já resolve isso automaticamente!
Veja Também
Vec— Vetor dinâmico — para armazenar e ordenar arestasHashMap— Mapa hash — para mapear nomes de vértices a índicesEq e Ord— Traits de comparação — usados na ordenação de arestas- Algoritmo de Prim — alternativa com fila de prioridade para MST
- Busca em Largura (BFS) — para verificar conectividade
- Busca em Profundidade (DFS) — alternativa para verificar conectividade