Time and Space Complexity
Lição 7 de 9 do curso Algoritmo de Kruskal - Algoritmos de Grafos da Coddy.
Complexidade de Tempo:
- Ordenar as E arestas é O(E log E); cada operação union-find é quase O(1) com compressão de caminho, então o Kruskal clássico é O(E log E). A versão de seleção mínima que construímos aqui é O(E2), o que é aceitável para grafos pequenos.
Complexidade de Espaço:
- O(V) para o array parent (além das arestas de entrada).
Resumo:
- O Kruskal expande uma MST adicionando a aresta livre de ciclos mais barata a cada passo, usando union-find para testar ciclos.
- Todas as MSTs compartilham o mesmo peso total, então a resposta é única.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Kruskal - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity