Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada para empilhar vértices a visitar durante a exploração?
- A) Lista encadeada
- B) Árvore binária
- C) Pilha (stack).
- D) Fila (queue)
- E) Tabela hash
✅ Resposta correta: alternativa C
Resolução passo a passo
- A busca em profundidade (DFS) explora o grafo indo o mais fundo possível por um caminho antes de retroceder. Na versão iterativa, isso é feito com uma estrutura que segue a regra LIFO (último a entrar, primeiro a sair).
- Essa estrutura é a pilha (stack). A cada vértice descoberto, ele é empilhado; o próximo vértice a ser visitado é o do topo da pilha, o que faz a exploração seguir sempre o caminho mais recente.
- Por que as outras estão erradas: a lista encadeada é apenas uma forma de armazenar dados, não define a ordem de remoção exigida pela DFS; a árvore binária é um tipo de grafo/estrutura de dados que o algoritmo percorre, não a estrutura auxiliar de controle; a fila (queue) segue a regra FIFO e produz a busca em largura (BFS), não a DFS; a tabela hash serve para busca rápida por chave e não define ordem de exploração.
- Conclusão: a alternativa C está correta e coincide com o gabarito oficial.
💡 Dica: Lembre-se da estrutura de dados utilizada na DFS.
Alternativa por alternativa
O aluno confunde a estrutura de armazenamento com a disciplina de acesso; acredita que qualquer lista encadeada basta para controlar a exploração.
O aluno associa DFS a árvores, pois a busca em profundidade é frequentemente ilustrada em árvores binárias, e não percebe que a estrutura auxiliar é outra.
A DFS explora caminhos em profundidade; a versão iterativa simula a recursão com uma pilha LIFO que armazena vértices a serem processados e permite retornar ao vértice anterior.
O aluno lembra que a busca em grafos usa filas, confundindo a BFS (busca em largura, FIFO) com a DFS (busca em profundidade, LIFO).
Por que engana: Confundir a pilha com a fila, escolhendo a fila como estrutura de dados para a busca em profundidade.
O aluno pensa que, por a hash permitir marcar rapidamente os vértices já visitados, ela é a estrutura central da exploração, confundindo controle de visitados com ordem de visita.
Raio-X da questão
busca em profundidade
avaliacao
estruturas de dados · algoritmos de busca
Revisar o funcionamento do algoritmo DFS e suas estruturas de dados.
Confundir a pilha com a fila, escolhendo a fila como estrutura de dados para a busca em profundidade.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
- Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog