Observe o grafo abaixo. Considerando que todos os vértices, à esquerda do vértice 4, já foram visitados. Qual o caminho percorrido, ao se realizar a busca em profundidade (interna), começando do vértice 4 em direção ao vértice 8?
Com base no exposto, assinale a alternativa correta.
Alternativas
Alternativa 1:
4, 8.
Alternativa 2:
4, 7, 8.
Alternativa 3:
4, 7, 11, 8.
Alternativa 4:
4, 8, 7, 12, 11.
Alternativa 5:
4, 7, 11, 12, 8.
Soluções para a tarefa
Realizando a busca em profundidade na teoria dos grafos, a resposta correta é Alternativa 5: 4, 7, 11, 12, 8.
A busca em profundidade também conhecido em inglês por Depth-First Search (DFS) é um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo.
O aprofundamento alcançando os seguintes nós assume que ele prossiga da esquerda para a direita, como mostra na imagem de exemplo.
Resposta:
Alternativa 5:
4, 7, 11, 12, 8.
Explicação:
Essa técnica faz com que todo um segmento do grafo seja visitado até o final, antes que uma nova porção seja investigada.
A partir de um primeiro nó, o algoritmo coloca todos os vértices adjacentes em uma pilha e marca o nó atual como visitado. Em seguida, o pega o nó do topo, desempilhando-o, e repete o processo. A busca segue até que o alvo seja encontrado ou que a pilha esteja vazia.
Isso faz com que a busca percorra um caminho no grafo até encontrar um nó que não tenha mais vértices adjacentes. Nesse momento, o algoritmo inicia uma nova busca a partir do último nó empilhado. Observe o comportamento na Figura.
