MO417 - Questão para a prova oral

Número: 2003-135

Enunciado: Em relação ao algoritmo tradicional conhecido como BFS (Breadth-First Search, ou Busca em Largura) em grafos, é CORRETO afirmar que:

A) O mesmo algoritmo pode ser usado quer o grafo de entrada seja representado com listas de adjacências ou com uma matriz de adjacências.
 
B) O algoritmo é executado em tempo linear no tamanho da representação com listas 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 número de arestas de um caminho mais longo desde o vértice origem s até um vértice qualquer v.
 
E) N.D.A.

Ideia original de: Marcelo Fantinato