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