Exemplo — Construindo a árvore geradora mínima
Vamos aplicar o algoritmo de Kruskal ao grafo ponderado abaixo. Cada aresta possui um peso, e o objetivo é selecionar as arestas mais leves possíveis sem formar ciclos.
A regra é sempre a mesma: ordenar as arestas por peso e adicionar apenas as que forem seguras.
Passo 1 — Ordenar as arestas
O algoritmo começa listando todas as arestas em ordem crescente de peso:
Essa etapa é essencial porque o Kruskal sempre tenta escolher a aresta mais barata disponível primeiro.
Mas “mais barata” não é suficiente: a aresta também precisa ser segura, ou seja, não pode fechar um ciclo.
Passo 2 — Aceitar as menores arestas seguras
Seguindo a ordem:
AC (1) é aceita.
AB (2) é aceita.
BD (3) é aceita.
CE (4) é aceita.
DF (5) é aceita.
Nesse ponto, todos os 6 vértices já estão conectados. Como uma árvore com 6 vértices deve ter exatamente 5 arestas, o algoritmo pode parar.
Passo 3 — Rejeitar arestas que formam ciclo
Suponha que tentamos adicionar a aresta CD (6).
Ela conectaria dois vértices que já estão ligados por um caminho: C → A → B → D. Portanto, adicionar CD criaria um ciclo.
Esse é exatamente o tipo de aresta que o Kruskal rejeita. A árvore deve permanecer conectada, mas sem ciclos.
Resultado final
A árvore geradora mínima encontrada é:
O peso total é: 1 + 2 + 3 + 4 + 5 = 15.
O algoritmo conectou todos os vértices sem formar ciclos e com o menor custo possível.
Intuição chave da Parte 2
O Kruskal não tenta encontrar a melhor árvore de uma vez só. Ele constrói a solução passo a passo.
A cada etapa, ele faz uma pergunta simples: esta é a menor aresta disponível que posso adicionar com segurança?
Na próxima parte, vamos entender como detectar ciclos de forma eficiente, usando a estrutura Union-Find.