Questão para a Prova Oral 143

Semana: 12/05/2003 a 16/05/2003

Assunto: Grafos (Parte 2) e Árvores Espalhadas Mínimas

Enunciado
Em relação aos algoritmos DFS e DFS-VISIT (Busca em Profundidade) de grafos, é INCORRETO afirmar:

A) Uma floresta produzida pela aplicação do algoritmo possui quatro tipos de arestas: arestas de árvores, arestas de retorno, arestas diretas e arestas cruzadas.
B) Independentemente da ordem na qual os vizinhos de um determinado vértice são visitados, o resultado da busca em profundidade é sempre o mesmo – ou seja, a árvore gerada é sempre a mesma.
C) O algoritmo é executado em tempo linear no tamanho da representação de Lista de Adjacências.
D) O algoritmo pressupõe que o grafo de entrada G = (V, E) é representado com o uso de uma Lista de Adjacências.
E) N.D.A.

Marcelo Fantinato
RA: 000472