MO417 - Questão para a prova oral

Número: 2009-118

Enunciado: Suponha, que, para resolver um determinado problema, você desenvolveu um algoritmo que utiliza grafos onde os pesos das arestas são porcentagens distribuidas uniformente de 0% a 100%. Suponha ainda que seja necessário encontrar a árvore geradora mínima destes grafos.

Considerando esta configuração particular, qual dos seguintes algoritmos possui menor complexidade de tempo de execução assitótico esperado? O algoritmo de Kruskal será implementado utilizando florestas de conjuntos disjuntos com heurísticas de união por posto e compressão de caminho.

1. Algoritmo de Kruskal, utilizando o algoritmo Bucket-Sort para ordenação;
2. Algoritmo de Kruskal, utilizando o algoritmo Merge-sort para ordenação;
3. Algoritmo de Prim, utilizando heap binário;
4. Algoritmo de Prim, utilizando heap de Fibonacci;
5. NDA

Ideia original de: Raoni Florentino da Silva Teixeira