Árvore Geradora Mínima de Kruskal
Adicione as arestas mais baratas sem criar ciclos.
Árvore Geradora Mínima de Kruskal é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que é uma MST
Uma árvore geradora mínima conecta todos os vértices usando o menor peso total possível das arestas, sem ciclos. Pense em instalar a fiação de uma cidade pelo menor custo. 🌲
Ideia central de Kruskal
O algoritmo de Kruskal segue uma estratégia puramente gulosa: continue adicionando a aresta mais barata que não crie um ciclo até que todo o grafo esteja conectado.
Etapa um: ordene as arestas
Primeiro, use sort para ordenar todas as arestas pelo peso, começando pela menor. Dar preferência às arestas baratas é o que torna o total final mínimo.
edges.sort() # (weight, u, v)Por que DSU se encaixa perfeitamente
Adicionar uma aresta forma um ciclo somente quando as duas extremidades já estão conectadas. DSU responde a essa verificação de conectividade em tempo quase constante. 🤝
Percorra as arestas ordenadas
Percorra as arestas da mais barata à mais cara. Para cada uma, verifique se as duas extremidades já compartilham uma raiz na DSU.
for w, u, v in edges:
ru, rv = find(u), find(v)Aceitar ou rejeitar
Se as raízes forem diferentes, a aresta conecta duas partes separadas; portanto, aceite a aresta e una as partes. Se as raízes forem iguais, ignore-a para evitar um ciclo.
if ru != rv:
union(u, v)
total += wSaiba quando parar
Uma árvore geradora com n vértices tem exatamente n menos 1 arestas. Depois de aceitar essa quantidade, você pode parar antecipadamente.
Detectando a desconexão
Se você terminar de percorrer todas as arestas tendo aceitado menos de n menos 1, o grafo está desconectado e não existe nenhuma árvore geradora.
O custo de tempo
A ordenação domina o custo, então o algoritmo de Kruskal é executado em O(E log E). As operações da DSU são tão baratas que quase não aumentam esse total.
Por que a estratégia gulosa está correta
A propriedade do corte garante que a aresta de menor peso que atravessa qualquer divisão pode ser adicionada com segurança. É exatamente por isso que escolher as arestas mais baratas primeiro nunca dá errado.
Quando escolher Kruskal
Kruskal se destaca em grafos esparsos fornecidos como uma lista de arestas, o formato que a maioria dos problemas de competição entrega diretamente. ⚡
Verificação rápida
Determine o que faz Kruskal rejeitar uma aresta.
Recapitulação
Você construiu a MST de Kruskal: ordene as arestas, adicione a mais barata que una dois componentes por meio da DSU e pare ao atingir n menos 1 arestas. 🎉
Perguntas Frequentes
A aula “Árvore Geradora Mínima de Kruskal” é grátis?
Sim — o texto completo de “Árvore Geradora Mínima de Kruskal” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Árvore Geradora Mínima de Kruskal”?
Adicione as arestas mais baratas sem criar ciclos. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Árvore Geradora Mínima de Kruskal”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- DSU com Compressão de Caminhos
- União por Classificação e Componentes
- Árvore Geradora Mínima de Kruskal
- MST de Prim com uma Heap