Problema — Como detectar ciclos de forma eficiente?
Na Parte 2, vimos que o algoritmo de Kruskal adiciona a aresta mais leve que não forma ciclo. Porém, em grafos grandes, verificar ciclos manualmente não é viável.
Para resolver isso de forma eficiente, utilizamos uma estrutura de dados chamada Union-Find, também conhecida como Disjoint Set Union (DSU).
Em vez de procurar caminhos no grafo, o Union-Find acompanha quais vértices já estão conectados.
O que o Union-Find faz?
A estrutura mantém os vértices organizados em conjuntos disjuntos, que representam componentes conectados.
Inicialmente, cada vértice está em seu próprio conjunto. À medida que o Kruskal aceita arestas, esses conjuntos são unidos.
Para verificar se uma aresta é segura, basta perguntar: os dois extremos pertencem ao mesmo conjunto?
As duas operações principais
O Union-Find possui duas operações fundamentais:
Find(x): retorna o representante do conjunto que contém x.
Union(x, y): une os conjuntos que contêm x e y.
No Kruskal, a regra fica:
se Find(u) ≠ Find(v), aceitamos a aresta e fazemos Union(u, v).
Por que isso evita ciclos?
Se dois vértices já estão no mesmo conjunto, então já existe um caminho conectando-os.
Adicionar uma nova aresta entre eles criaria um laço, ou seja, um ciclo.
Se estiverem em conjuntos diferentes, a aresta apenas conecta dois componentes distintos.
Exemplo com conjuntos
Suponha que temos:
Se analisarmos a aresta C–D, os vértices pertencem a conjuntos diferentes, então a aresta é aceita.
Após isso:
Agora, adicionar uma aresta entre B e C seria rejeitado, pois já estão conectados.
Por que isso é importante?
O Kruskal processa muitas arestas. Sem uma estrutura eficiente, a verificação de ciclos seria lenta.
O Union-Find torna essa verificação muito rápida, especialmente com otimizações como compressão de caminho (path compression) e união por rank (union by rank).
Por isso, a combinação ordenação + Union-Find é a forma clássica de implementar o Kruskal.
Pseudocódigo conceitual
1. Ordenar arestas por peso
2. Inicializar cada vértice em seu próprio conjunto
3. Para cada aresta (u, v):
• se Find(u) ≠ Find(v), aceitar aresta
• Union(u, v)
4. Parar após n − 1 arestas
A detecção de ciclos é reduzida a uma simples comparação entre representantes.
Intuição chave da Parte 3
O Union-Find não precisa conhecer toda a estrutura do grafo. Ele guarda apenas o essencial: quais vértices já estão conectados.
Isso é suficiente para o Kruskal tomar decisões corretas de forma rápida e eficiente.
Na próxima parte, vamos comparar o Kruskal com o algoritmo de Prim, e entender quando cada um é mais adequado.