MO417 - Questão para a prova oral
Número: 118
Enunciado:
Suponha, que, para resolver um determinado problema,
você desenvolveu um algoritmo que constrói grafos compostos
por um conjunto de vétices de tamanho |V| e por um conjunto de
arestas ponderadas de tamanho |E| distribuidas uniformente por peso.
Suponha ainda, que para completar sua solução é necessário
encontrar a árvore geradora mínima destes grafos.
Considerando essa configuração particular,
qual dos seguintes algoritmos possui menor complexidade de
tempo de execução assitótico?
O algoritmo de Kruskal será implementado utilizando florestas
de conjuntos disjuntos com heurísticas
de união por posto e compressão de caminho.
Autor(a): Raoni Florentino da Silva Teixeira