Questão para a Prova Oral 132
10ª Semana: 05/05/2003 a 09/05/2003
Estruturas de dados para conjuntos disjuntos &
Algoritmos elementares de grafos

Enunciado
Sobre grafos, assinale a alternativa CORRETA:

A) Há apenas duas estruturas de dados que dão suporte à representação de grafos: listas de adjacências e matrizes de adjacências, sendo a lista de adjacências mais utilizada por ser de implementação mais simples.

B) A representação por matriz de adjacência normalmente é preferida para a representação de grafos esparsos (para os quais o número de arestas é muito menor ao quadrado do número de vértices), já que fornece um modo compacto de representá-los.

C) O algoritmo BFS (G, s) apresentado pelo livro (capitulo 22) produz uma árvore contendo um dado vértice s como raiz, e todos os vértices alcançáveis por ele em G.

D) O algoritmo BFS funciona apenas para grafos não-orientados, já que para grafos orientados as distâncias entre s e os outros vértices calculadas pelo algoritmos não seriam mínimas.

E) N.D.A.

Autora: Camila Ribeiro Rocha
RA: 022247