Kruskal’s Algorithm

Kruskal’s Algorithm: O que é?

O Algoritmo de Kruskal é um algoritmo na teoria dos grafos que encontra a árvore geradora mínima (MST) para um grafo ponderado conectado. Isso significa que ele encontra um subconjunto das arestas que forma uma árvore que inclui todos os vértices, onde o peso total de todas as arestas na árvore é minimizado. É um algoritmo guloso porque, em cada passo, ele escolhe a aresta de menor peso que não forma um ciclo com as arestas já selecionadas.

Como Funciona o Algoritmo de Kruskal?

O algoritmo segue os seguintes passos:

1. Ordenar as Arestas: Comece ordenando todas as arestas do grafo em ordem crescente de peso.
2. Inicializar a Árvore: Inicialize uma floresta de árvores, onde cada vértice do grafo é uma árvore separada.
3. Iterar pelas Arestas Ordenadas: Percorra as arestas ordenadas. Para cada aresta (u, v):
   • Verificar Ciclos: Verifique se os vértices ‘u’ e ‘v’ pertencem à mesma árvore. Isso pode ser feito usando uma estrutura de dados chamada Union-Find (ou Disjoint-Set).
   • Adicionar à Árvore: Se ‘u’ e ‘v’ pertencem a árvores diferentes, adicione a aresta (u, v) à árvore geradora mínima e una as duas árvores em uma única árvore.
4. Repetir: Repita o passo 3 até que todos os vértices estejam conectados em uma única árvore.

Union-Find (Disjoint-Set) e o Algoritmo de Kruskal

A estrutura de dados Union-Find (ou Disjoint-Set) é crucial para a eficiência do algoritmo de Kruskal. Ela permite determinar rapidamente se dois vértices pertencem à mesma árvore e unir duas árvores em uma única árvore. As operações principais são:

• Find(x): Encontra o representante (raiz) da árvore à qual o vértice ‘x’ pertence.
• Union(x, y): Une as árvores que contêm os vértices ‘x’ e ‘y’.

Implementações eficientes de Union-Find, como a compressão de caminho e a união por rank, garantem que as operações Find e Union tenham um custo amortizado quase constante, tornando o algoritmo de Kruskal muito eficiente.

Complexidade do Algoritmo de Kruskal

A complexidade de tempo do algoritmo de Kruskal é dominada pela ordenação das arestas e pelas operações Union-Find. Se o grafo tem ‘E’ arestas e ‘V’ vértices:

• Ordenação: A ordenação das arestas leva O(E log E) tempo.
• Union-Find: As operações Union-Find levam O(E α(V)) tempo, onde α(V) é a função inversa de Ackermann, que cresce extremamente lentamente e pode ser considerada praticamente constante para todos os propósitos práticos.

Portanto, a complexidade total do algoritmo de Kruskal é O(E log E). Como E pode ser no máximo V², e log(V²) = 2 log V, a complexidade também pode ser expressa como O(E log V).

Aplicações do Algoritmo de Kruskal

O algoritmo de Kruskal tem diversas aplicações práticas, incluindo:

• Redes de Computadores: Encontrar a forma mais barata de conectar todos os computadores em uma rede.
• Redes de Transporte: Planejar rotas de transporte minimizando o custo total da construção de estradas ou ferrovias.
• Redes de Energia: Projetar redes de distribuição de energia elétrica de forma eficiente.
• Análise de Clusters: Agrupar dados em clusters com base na similaridade entre os pontos de dados.

Kruskal’s Algorithm vs. Prim’s Algorithm

Tanto o algoritmo de Kruskal quanto o algoritmo de Prim são algoritmos gulosos para encontrar a árvore geradora mínima. A principal diferença é a forma como eles constroem a árvore:

• Kruskal: Começa com uma floresta de árvores e adiciona arestas de menor peso que não formam ciclos, unindo as árvores gradualmente.
• Prim: Começa com um único vértice e adiciona arestas de menor peso que conectam o vértice atual à árvore em crescimento.

Em geral, o algoritmo de Kruskal é mais adequado para grafos esparsos (com poucas arestas), enquanto o algoritmo de Prim é mais adequado para grafos densos (com muitas arestas). A escolha do algoritmo depende das características específicas do grafo.