Question

Questão 9

A busca em profundidade de baseia no conceito de pilha, no qual para cada nó que está no topo da pilha, é preciso visitar o seu próximo nó adjacente, empilhando-o, de maneira recorrente. Observe o algoritmo DFS(), abaixo:



Assim sendo, aplique o algoritmo acima no grafo representado abaixo, considerando que a busca se inicia no vértice 1.



A sequência de visitação que corresponde à resposta correta é:

Alternativa 1:
1, 2, 5, 6, 7, 4, 3.

Alternativa 2:
1, 2, 5, 3, 4, 7, 6.

Alternativa 3:
1, 2, 3, 5, 4, 7, 6.

Alternativa 4:
1, 3, 4, 7, 6, 5, 2.

Alternativa 5:
1, 3, 5, 2, 4, 6, 7.

Answer 1

A sequência de visitação correta é a seguinte: Alternativa 2: 1, 2, 5, 3, 4, 7, 6.

A procura por profundidade tem como base o conceito de pilha, onde cada um dos nós que se encontram no topo da pilha precisa de uma visitação ao seu próximo nó que se encontra adjacente. Sendo que esses nós se encontram em um formato de pilha e ocorrem de forma recorrente.

Ao considerar o algoritmo DFS() e sua aplicação levando em conta a busca com início no vértice 1, temos que a correta sequência de visitação consiste em: 1, 2, 5, 3, 4, 7, 6.

Bons estudos!