Please enable JavaScript.
Coggle requires JavaScript to display documents.
Kruskal’s Algorithm - Coggle Diagram
Kruskal’s Algorithm
Algoritmo guloso que busca uma árvore de abrangência mínima em um grafo ponderado.
Inicia com uma lista vazia e adiciona arestas em ordem crescente de peso, evitando ciclos.
A cada adição, verifica se a inclusão da aresta cria um ciclo.
Eficiência:
Depende da estrutura de dados usada.
Utiliza operações de união e busca em conjuntos disjuntos.
Combinação de Union by Size/ Rank com Compressão de Caminho.
Eficiência próxima à linear para sequências de operações de união e busca.
Implementações:
Quick Find:
Usa uma matriz para representar os conjuntos.
Eficiente para operações de busca.
Ineficiente para operações de união.
Quick Union:
Representa conjuntos como árvores enraizadas.
Eficiente para operações de união.
Pode degenerar em árvores altas.
Melhorias:
Union by Size: Anexa a árvore menor à maior.
Union by Rank: Anexa a árvore com menor altura à de maior altura.
Compressão de Caminho: Redireciona nós durante operações de busca.