MO417 - Questão para a prova oral

Número:

Enunciado: Considere que um vértice s é descoberto na primeira vez em que é encontrado durante o procedimento de busca em largura ou em profundidade. Considere também que quando possível, vértices de numeração menor são descobertos primeiro, ou seja, numa dada interação onde 1 e 2 são vértices adjacentes a s, o vértice 1 é descoberto primeiro.

Dado o grafo abaixo, partindo do vértice 1, defina qual dos dois algoritmos descobre mais rápido os vértices 4, 7 e 8, respectivamente. Isto quer dizer que, o algoritmo X descobre o vértice s percorrendo menos vértices do que o algoritmo Y percorre.

a) busca em profundidade, profundidade e largura

b) busca em profundidade, largura e profundidade

c) busca em largura, profundidade e largura

d) busca em largura, largura e largura
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo