--- title: "Algoritmo de Kruskal em Rust" url: "https://rustlang.com.br/algoritmos/kruskal/" markdown_url: "https://rustlang.com.br/algoritmos/kruskal.MD" description: "Implementação completa do algoritmo de Kruskal em Rust com Union-Find, árvore geradora mínima, diagramas visuais e análise de complexidade." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Algoritmo de Kruskal em Rust Implementação completa do algoritmo de Kruskal em Rust com Union-Find, árvore geradora mínima, diagramas visuais e análise de complexidade. 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: 1. Ordena todas as arestas do grafo por peso (menor para maior). 2. Inicializa uma estrutura Union-Find com cada vértice em seu próprio conjunto. 3. 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). 4. 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. ```rust /// 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 { 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) ```rust /// Estrutura Union-Find com compressão de caminho e união por rank. struct UnionFind { pai: Vec, rank: Vec, } 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 ```rust #[derive(Clone, Debug)] struct Aresta { u: usize, v: usize, peso: u64, } struct UnionFind { pai: Vec, rank: Vec, } 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) -> (Vec, 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 ```rust #[derive(Clone, Debug)] struct Aresta { u: usize, v: usize, peso: u64, } struct UnionFind { pai: Vec, rank: Vec, 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, ) -> Option<(Vec, 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](/algoritmos/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 1. **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. 2. **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. 3. **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. 4. **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](/stdlib/vec/) — para armazenar e ordenar arestas - [`HashMap` — Mapa hash](/stdlib/hashmap/) — para mapear nomes de vértices a índices - [`Eq e Ord` — Traits de comparação](/stdlib/eq-ord/) — usados na ordenação de arestas - [Algoritmo de Prim](/algoritmos/prim/) — alternativa com fila de prioridade para MST - [Busca em Largura (BFS)](/algoritmos/bfs/) — para verificar conectividade - [Busca em Profundidade (DFS)](/algoritmos/dfs/) — alternativa para verificar conectividade