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
- Caminhões descarregam suprimentos em uma central que atende localidades isoladas após fortes chuvas. O depósito possui…
- Por que certos pedidos de melhoria no bairro demoravam a chegar ao responsável pela decisão? Para responder a essa…
- Ao final de uma oficina de montagem, uma turma precisou guardar 24 peças de encaixe usadas em atividades com tablets e…
- No fim da tarde, um grupo de jovens voluntários recebeu caixas de livros devolvidos por moradores do bairro. Para evitar…
- Em computação, defina sucintamente o que é um grafo simples não direcionado e explique o papel de vértices e arestas na…
- Descreva em pseudocódigo um algoritmo que, dada uma matriz 'votos' onde cada linha é um registro [urnaID, candidato]…
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