Problema — Conectando uma rede com custo mínimo
Suponha que queremos conectar várias cidades usando cabos, estradas ou tubulações. Cada possível conexão tem um custo, e o objetivo é conectar todas as cidades gastando o mínimo possível.
Em teoria dos grafos, isso se torna um problema de encontrar uma árvore geradora mínima: um conjunto de arestas que conecta todos os vértices, não possui ciclos e tem o menor custo total possível.
O que é o algoritmo de Kruskal?
O algoritmo de Kruskal é um método guloso para encontrar uma árvore geradora mínima em um grafo ponderado. Ele funciona analisando as arestas da menor para a maior.
A cada passo, o algoritmo tenta adicionar a aresta de menor peso disponível. Porém, uma aresta só é aceita se ela não formar um ciclo.
Esse processo continua até que todos os vértices estejam conectados. Se o grafo tem n vértices, a árvore final terá exatamente n − 1 arestas.
A intuição central é simples: escolher sempre a aresta mais barata que seja segura. “Segura” significa que ela conecta componentes diferentes, em vez de fechar um ciclo.
Por sempre escolher a melhor opção local possível, o Kruskal é um dos exemplos mais claros e elegantes de algoritmo guloso na teoria dos grafos.
Por que essa ideia é importante?
Árvores geradoras mínimas são úteis sempre que queremos construir uma estrutura conectada com custo mínimo: redes de comunicação, sistemas elétricos, estradas, clusterização e infraestrutura em geral.
O algoritmo de Kruskal também é importante do ponto de vista didático, pois mostra como uma regra local pode gerar uma solução global ótima.
Na prática, ele é especialmente natural quando o grafo é visto como um conjunto de arestas ponderadas, já que o algoritmo começa ordenando essas arestas.
Intuição chave da Parte 1
O objetivo não é apenas conectar o grafo — é conectá-lo com o menor custo possível.
O Kruskal faz isso perguntando repetidamente: qual é a menor aresta que posso adicionar agora sem quebrar a estrutura de árvore?
Na próxima parte, vamos executar o algoritmo passo a passo, ordenando as arestas e decidindo quais são aceitas ou rejeitadas.