kim

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre os algoritmos de grafos, assinale a alternativa que contém os itens corretos:

I - O algoritmo de Prim tem desempenho equivalente ao algoritmo de Kruskal quando o grafo é esparso.

II - O Algoritmo de Bellman-Ford tem desempenho superior ao algoritmo de Dijkstra em grafos orientados com pesos negativos.

III - A ordenação topológica de um grafo utiliza a busca em profundidade para encontrar o tempo de término de cada vértice, e dessa forma organizar os vértices de forma que eles fiquem ordenados decrescentemente pelo tempo de término. O algoritmo só funciona em grafos acíclicos não-orientados.

IV - Durante a execução do algoritmo de busca em profundidade, encontrar uma aresta de retorno indica que o grafo não é acíclico.

V - A melhor estrutura de dados para o algoritmo de Prim são as Heaps de Fibonacci, fazendo a complexidade do algoritmo ser O(E + V lg V).

(a) I, II e IV.

(b) II, III e V.

(c) I, IV e V.
(d) II, IV e V. 

(e) N.D.A 

Idéia original de: Kim Pontes Braga