Para identificar novas aplicações que utilizem grafos é útil que os analistas detenham conhecimentos sobre o funcionamento das técnicas aplicadas aos mesmos. Considerando o vértice 1 como sendo o nó inicial, execute algoritmo de busca em profundidade no grafo abaixo.
Após realizada a busca em profundidade, assinale a alternativa que representa a ordem em que os vértices são visitados.
Alternativas
Alternativa 1:
1, 2, 3, 4, 5, 6, 7, 8.
Alternativa 2:
1, 2, 4, 5, 3, 6, 7, 8.
Alternativa 3:
1, 2, 3, 5, 4, 6, 8, 7.
Alternativa 4:
1, 2, 6, 3, 4, 7, 8, 5.
Alternativa 5:
5, 3, 8, 1, 2, 4, 6, 7.
Soluções para a tarefa
Resposta:
Alternativa 3: 1,2,3,5,4,6,78
Explicação:
No enunciado ele fala de PROFUNDIDADE, e não LARGURA.
Resposta:
(busca em profundidade) FIGURA 1 seria 1, 2, 3, 4, 5, 6, 7, 8.
EX:''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.''
SERIA 1, 2, 6, 3, 4, 7, 8, 5. EM FIGURA 2 (busca em largura).
"Nós visitados são enfileirados ao invés de empilhados. Isso garante, primeiramente, que sejam percorridos todos os nós adjacentes ao nó atual para, só então, visitar os nós mais distantes, repetindo o processo."pg120 do livro
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.
EX DO LIVRO:
"A busca em largura, quando aplicada ao grafo da Figura , resultaria na seguinte ordem de visitação: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. "
1, 2, 3, 5, 4, 6, 8, 7. e não 1,2,3,5,4,6,78.
Afinal. é a alternativa 3 mesmo ou não ?