Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é usada para manter os vértices a visitar na ordem correta?
- A) Uma lista encadeada.
- B) Uma árvore binária.
- C) Uma pilha (stack).
- D) Um vetor estático.
- E) Uma fila (queue) FIFO.
✅ Resposta correta: alternativa E
Resolução passo a passo
- O BFS (busca em largura) percorre o grafo por níveis: visita primeiro o vértice inicial, depois todos os seus vizinhos, depois os vizinhos dos vizinhos, e assim por diante.
- Para que essa ordem por níveis seja respeitada, os vértices descobertos precisam ser processados na ordem em que foram descobertos, ou seja, o primeiro a entrar deve ser o primeiro a sair (FIFO).
- Essa disciplina é exatamente a de uma fila (queue). Ao remover o vértice da frente, inserimos no fim da fila seus vizinhos ainda não visitados.
- Por isso a alternativa E está correta, e ela coincide com o gabarito oficial.
- Sobre as demais: a lista encadeada é apenas uma forma de implementar armazenamento e não define a ordem de remoção; a árvore binária é uma estrutura hierárquica que não serve como fila de visitação; a pilha (LIFO) faz a busca seguir em profundidade, que é o DFS, e não o BFS; o vetor estático é apenas um arranjo de memória, sem política de ordem própria.
💡 Dica: Lembre-se da estrutura de dados utilizada no BFS.
Alternativa por alternativa
Confunde a estrutura de armazenamento com a política de ordem: acha que basta uma lista para manter os vértices na ordem correta, sem perceber que é preciso remover sempre o mais antigo.
Associa o percurso em grafos a estruturas de árvore, imaginando que a árvore binária organiza os vértices a visitar; o BFS usa uma fila e não uma árvore binária de busca.
Acredita que a pilha serve para qualquer busca, esquecendo que a pilha (LIFO) faz o último descoberto ser visitado primeiro, o que caracteriza o DFS e não o BFS.
Por que engana: Confundir a estrutura de dados correta, escolhendo uma pilha em vez de uma fila, pois o BFS utiliza a abordagem FIFO.
Pensa que um vetor de tamanho fixo basta para manter a ordem de visita, ignorando que o problema exige política de remoção FIFO, e não apenas espaço para armazenar.
BFS explora níveis em ordem crescente de distância; uma fila garante processamento por ordem de descoberta (FIFO), preservando camadas.
Raio-X da questão
algoritmo BFS
avaliacao
estruturas de dados · algoritmos de busca
Revisar as estruturas de dados utilizadas em algoritmos de busca.
Confundir a estrutura de dados correta, escolhendo uma pilha em vez de uma fila, pois o BFS utiliza a abordagem FIFO.
ciencia_tecnologia
tomada_decisao
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 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)?
- Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
Todas as questões de Organização e representação da informação
🔎 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