Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
- A) Pilha (estrutura LIFO)
- B) Vetores estáticos
- C) Matriz de adjacência
- D) Fila (estrutura FIFO).
- E) Lista de arestas ordenadas
✅ Resposta correta: alternativa D
Resolução passo a passo
- A travessia em largura (BFS) visita os vértices por níveis: primeiro o vértice inicial, depois todos os seus vizinhos diretos, depois os vizinhos dos vizinhos, e assim por diante.
- Para isso, é preciso processar os vértices na ordem em que foram descobertos, ou seja, o primeiro que entra é o primeiro a ser explorado. Essa disciplina é a FIFO (First In, First Out), típica da fila.
- Com a fila, ao retirar um vértice, enfileira-se seus vizinhos ainda não visitados; assim, todos os vértices de um nível são processados antes dos do nível seguinte, o que garante a propriedade de caminho mínimo em número de arestas em grafos não ponderados.
- Por que as outras estão erradas: A) a pilha (LIFO) produz a travessia em profundidade (DFS), não em largura; B) vetores estáticos são uma forma de armazenamento sem política de acesso que produza a ordem por níveis, e não atendem à ordem de processamento exigida; C) a matriz de adjacência é uma forma de representar o grafo, não uma estrutura para controlar a ordem de visita; E) uma lista de arestas ordenadas não define a ordem de exploração dos vizinhos necessária ao BFS.
- Conclusão: a estrutura mais adequada é a fila (alternativa D), que coincide com o gabarito oficial.
💡 Dica: Considere as estruturas de dados utilizadas em algoritmos de grafos.
Alternativa por alternativa
O aluno associa a busca em grafos a qualquer exploração sistemática e escolhe a pilha, confundindo a travessia em largura com a travessia em profundidade, que usa pilha (ou recursão).
Por que engana: Confundir a estrutura de dados adequada para BFS, escolhendo uma que não permite a travessia em largura, como a pilha.
O aluno acredita que a escolha da estrutura depende apenas de armazenar os vértices, sem considerar a política de remoção necessária para visitar por níveis.
O aluno confunde a estrutura usada para representar o grafo com a estrutura que controla a ordem de visita, achando que a matriz de adjacência determina o caminhamento.
BFS explora vértices por níveis a partir da origem; a fila mantém ordem FIFO para processar primeiro os vértices de menor distância, garantindo visita por camadas.
O aluno pensa que ordenar as arestas permite explorar os vizinhos por níveis, sem perceber que o BFS depende da ordem de processamento dos vértices descobertos, não de uma ordenação global das arestas.
Raio-X da questão
travessia em largura
avaliacao
estruturas de dados · grafo não orientado
Revisar as estruturas de dados para algoritmos de grafos.
Confundir a estrutura de dados adequada para BFS, escolhendo uma que não permite a travessia em largura, como a pilha.
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 uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de…
- 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 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…
- Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas de…
🔎 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