Question

O algoritmo de busca em profundidade em grafos conexos faz com que todo um segmento do grafo seja visitado até o final, antes que uma nova porção seja investigada.

PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).


Baseado em nosso livro de estudo, leia as afirmativas a seguir sobre os passos do algoritmo de busca em profundidade e assinale a alternativa correta.

I - A partir do último nó do grafo, o algoritmo monta uma pilha com os vértices adjacentes.
II - Após percorrer os seus vértices adjacentes, o nó em processamento é marcado como visitado.
III - Uma vez formada a pilha de nós, o algoritmo pega o último nó empilhado e repete o processo de percorrê-lo.
IV - O processamento do algoritmo termina quando o valor procurado é encontrado no grafo ou a pilha fica vazia, o que significa que todos os nós foram percorridos e o valor não foi encontrado no grafo.

Answer 1

Alternativa 3:

Apenas II e IV estão corretas.

Answer 2

apenas II eIII estão correstas.

IV - O processamento do algoritmo termina quando o valor procurado é encontrado no grafo ou a pilha fica vazia, o que significa que todos os nós foram percorridos e o valor não foi encontrado no grafo.

a IV está errada por que os valores são encontrados.