ade

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Considere o grafo abaixo, execute uma busca em profundidade. Suponha que as listas de adjacências estejam em ordem alfabética. Toda vez que for reiniciá-lo, pegue o primeiro vértice em ordem alfabética que ainda não foi visitado.
Com base na classificação das arestas da busca em profundidade, pode-se dizer que o algoritmo encontrará durante o percurso:

Lembrete: 

I) Arestas de Árvore: faz parte de uma árvore de busca em profundidade;

II) Aresta de Retorno: liga um descendente a um ancestral;

III) Arestas Diretas: liga um ancestral a um descendentes;

IV) Arestas Cruzadas: as demais.

a) 7 Arestas de Árvore e 2 Arestas de Retorno
b) 2 Arestas de Diretas e 2 Arestas de Cruzadas
c) 8 Arestas de Árvore e 1 Arestas de Retorno
d) 2 Arestas de Diretas e 3 Arestas de Cruzadas
e) NDA 
Ideia original de: Ademar Takeo Akabane