Algoritmo de Kruskal
Última atualização
O algoritmo de Kruskal constrói uma árvore geradora mínima (MST): o conjunto de arestas mais barato que conecta todos os nós sem ciclos. Ele ordena todas as arestas por peso e depois adiciona gulosamente a próxima aresta mais barata desde que ela una dois nós que ainda não estejam conectados. Pressione reproduzir acima para ver a árvore crescer, uma aresta segura e barata de cada vez.
A verificação de "já conectados?" é feita com uma estrutura de dados union-find (conjuntos disjuntos): cada aresta é descartada se seus dois extremos já estiverem no mesmo componente, porque adicioná-la formaria um ciclo. A ordenação domina o custo, resultando em O(E log E) no total. Kruskal se destaca em grafos esparsos.
Complexidade de tempo e espaço
| Medida | Complexidade | Notas |
|---|---|---|
| Tempo | O(E log E) | Dominado pela ordenação das arestas |
| Operações union-find | ≈ O(E α(V)) | Quase constante por verificação com compressão de caminhos |
| Espaço | O(V + E) | Lista de arestas + estrutura de conjuntos disjuntos |
| Melhor para | Grafos esparsos | Funciona a partir de uma lista global de arestas |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Ordene cada aresta por peso, de forma crescente. |
| 2 | Coloque cada nó em seu próprio componente (union-find). |
| 3 | Pegue a próxima aresta mais barata. |
| 4 | Se seus extremos estiverem em componentes diferentes, adicione-a à árvore e una-os. |
| 5 | Caso contrário, descarte-a (criaria um ciclo). |
| 6 | Pare quando a árvore tiver V − 1 arestas. |
Exemplo resolvido
Grafo com nós A, B, C, D e arestas A-B(1), B-C(2), A-C(3), C-D(4), B-D(5). Arestas ordenadas: A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):
| Aresta (peso) | Componentes antes | Ação |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | Componentes diferentes - adicionar à MST, unir em {A,B}. |
B-C(2) | {A,B} {C} {D} | Componentes diferentes - adicionar à MST, unir em {A,B,C}. |
A-C(3) | {A,B,C} {D} | A e C já estão juntos - descartar (formaria um ciclo). |
C-D(4) | {A,B,C} {D} | Componentes diferentes - adicionar à MST, unir em {A,B,C,D}. |
| Parar | {A,B,C,D} | A árvore tem V - 1 = 3 arestas. MST = A-B, B-C, C-D, peso total 7. |
Quando usar o algoritmo de Kruskal
| Use quando | Evite quando |
|---|---|
| O grafo é esparso (poucas arestas em relação aos nós). | O grafo é denso - Prim com um heap costuma ser mais rápido. |
| As arestas já estão disponíveis como uma lista global que você pode ordenar. | As arestas só chegam por listas de adjacência que você precisa percorrer por nó. |
| Você quer uma implementação simples apoiada em union-find. | Você precisa que a árvore cresça a partir de um nó inicial específico. |
| Você quer construir uma floresta geradora de um grafo desconexo. | Você precisa lidar com arestas chegando em fluxo sem uma ordenação completa. |
Código de Kruskal's Algorithm
Uma implementação limpa e executável de Kruskal's Algorithm em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Kruskal's Algorithm em Python
Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)Código de Kruskal's Algorithm em JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);Código de Kruskal's Algorithm em Java
Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}Código de Kruskal's Algorithm em C++
C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}Código de Kruskal's Algorithm em C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}Perguntas frequentes sobre o algoritmo de Kruskal
O que é uma árvore geradora mínima?
Uma árvore geradora mínima (MST) de um grafo ponderado conexo é um subconjunto de arestas que conecta todos os nós sem ciclos e com o menor peso total possível. Ela tem exatamente
V - 1 arestas para V nós.Qual é a diferença entre o algoritmo de Kruskal e o de Prim?
Ambos constroem uma árvore geradora mínima de forma gulosa. Kruskal ordena todas as arestas globalmente e adiciona a mais barata que não forme um ciclo, usando union-find. Prim faz uma única árvore crescer para fora a partir de um nó inicial, sempre adicionando a aresta mais barata que sai da árvore. Kruskal serve para grafos esparsos; Prim (com um heap) para os densos.
Por que o algoritmo de Kruskal usa union-find?
Antes de adicionar uma aresta, Kruskal precisa verificar se seus dois extremos já estão conectados - adicionar tal aresta criaria um ciclo. O union-find (conjuntos disjuntos) responde a "estão no mesmo componente?" e funde componentes em tempo amortizado quase constante, o que mantém o algoritmo eficiente.
Quando devo usar o algoritmo de Kruskal em vez do de Prim?
Prefira Kruskal quando o grafo é esparso e você já tem todas as arestas como uma lista que pode ordenar - a ordenação
O(E log E) é barata quando E é pequeno. O algoritmo de Prim com um heap binário ou de Fibonacci tende a vencer em grafos densos onde E se aproxima de V², porque evita ordenar todas as arestas de antemão.O algoritmo de Kruskal funciona em grafos desconexos?
Sim. Se o grafo é desconexo, Kruskal simplesmente não consegue alcançar
V - 1 arestas e, em vez disso, produz uma floresta geradora mínima - uma MST por componente conexo. Isso surge naturalmente porque o union-find nunca funde nós que não têm caminho entre si.Qual é o erro mais comum ao implementar o algoritmo de Kruskal?
Omitir a compressão de caminhos e a união por rank do union-find, o que degrada cada verificação de conectividade de quase constante para quase linear e pode dominar o tempo de execução. Outro erro frequente é esquecer de realmente unir os dois componentes após adicionar uma aresta, o que permite que arestas posteriores criem ciclos.
Recursos relacionados
Mais visualizações
