Questão para a Prova Oral 135

Semana: 05/05/2003 a 09/05/2003

Assunto: Conjuntos Disjuntos e Grafos (Parte 1)

Enunciado
Em relação ao algoritmo BFS (Busca em Largura) de grafos, é CORRETO afirmar:

A) O algoritmo pressupõe que o grafo de entrada G = (V, E) é representado com o uso de uma Matriz de Adjacências.
B) O algoritmo é executado em tempo linear no tamanho da representação de Lista de Adjacências.
C) Independentemente da ordem na qual os vizinhos de um determinado vértice são visitados, o resultado da busca em largura é sempre o mesmo – ou seja, a árvore gerada é sempre a mesma.
D) Um dos resultados do algoritmo é o valor do caminho mais longo desde um vértice origem s até um vértice qualquer v.
E) N.D.A.

Marcelo Fantinato
RA: 000472