Motivation

Kruskal mantém a floresta crescente de arestas escolhidas em uma estrutura union-find. Para adicionar uma aresta com segurança, ele verifica se as duas extremidades já estão no mesmo conjunto (o que criaria um ciclo).

Por que aprender Kruskal?

• MSTs reais: design de rede, agrupamento (clustering) e instalação de cabos ou estradas com custo mínimo.
• Union-find: uma estrutura bonita e reutilizável para rastrear conectividade que aparece em toda a ciência da computação.
• Corretude gulosa: outro exemplo onde sempre escolher a opção segura mais barata produz o ótimo global.

Todas as árvores geradoras mínimas de um grafo usam o mesmo multiconjunto de pesos de arestas, portanto o peso total (e a maior aresta) é único.