Computação3º anoBNCC EF15CO02Média⏱ medio

Na tabela de arestas: A-B, B-C, C-D, E-F, aplique o algoritmo de busca em largura (BFS) para determinar…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF15CO02

Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Na tabela de arestas: A-B, B-C, C-D, E-F, aplique o algoritmo de busca em largura (BFS) para determinar quantos nós pertencem ao componente conectado que contém B.

A) 6 nós
B) 4 nós
C) 3 nós
D) 2 nós
E) 5 nós

✅ Resposta correta: alternativa B

Resolução passo a passo

Identifique o grafo a partir da tabela de arestas: A-B, B-C, C-D e E-F. Como as arestas não têm direção, cada uma liga os dois vértices nos dois sentidos.
Comece a BFS no nó B e coloque-o na fila. Visite B e marque-o como visitado.
Retire B da fila e examine seus vizinhos diretos, que são A (pela aresta A-B) e C (pela aresta B-C). Adicione A e C à fila e marque ambos como visitados.
Retire A da fila. A não tem outros vizinhos além de B, que já foi visitado. Retire C da fila e examine seus vizinhos: B já foi visitado e D (pela aresta C-D) ainda não, então adicione D à fila.
Retire D da fila. Seus únicos vizinhos são C, já visitado. A fila fica vazia e a busca termina.
Os nós visitados são A, B, C e D, totalizando 4 nós. O componente formado por E-F não está conectado a B, então não entra na contagem.
Conclusão: o componente conectado de B tem 4 nós, o que corresponde à alternativa B, igual ao gabarito oficial.
Por que as outras estão erradas: a alternativa A considera os 6 nós do grafo, mas E e F não estão ligados a B; a alternativa C deixa de fora o nó A, que está ligado a B; a alternativa D interrompe a busca cedo demais; a alternativa E inclui o nó E, que pertence a outro componente.

💡 Dica: Aplique o algoritmo BFS a partir do nó B.

Alternativa por alternativa

A Erradaerro: Conceituala que mais engana

Contou todos os vértices que aparecem na tabela (A, B, C, D, E e F) sem verificar se E e F estão conectados a B. Tratou o grafo inteiro como se fosse um único componente.

Por que engana: O aluno pode contar erroneamente os nós, ignorando conexões diretas ou indiretas entre eles.

B Correta

BFS alcança A, B, C e D no mesmo componente, totalizando quatro nós.

C Erradaerro: Interpretação

Esqueceu que a aresta A-B também liga A a B, por considerar apenas as arestas que seguem a ordem B-C e C-D. Assim excluiu o nó A do componente.

D Erradaerro: Procedimental

Interrompeu a BFS antes de expandir todos os níveis, contando apenas B e C, e não seguiu a aresta C-D nem a aresta A-B. Esse erro vem de parar a busca cedo demais, sem processar toda a fila.

E Erradaerro: Conceitual

Incluiu o nó E no componente de B, achando que E-F faz parte da mesma conexão, ou somou indevidamente um nó de outro componente aos quatro nós corretos.

Raio-X da questão

Dificuldade Média

Bloom Aplicar

Leitura medio

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade unica

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 consolidacao

🎯 Conceito central

busca em largura

📌 Objetivo

avaliacao

🧱 Pré-requisitos

representacao de grafos · busca em profundidade

📚 Reveja

Revisar o algoritmo de busca em largura (BFS).

⚠️ Erro mais comum

O aluno pode contar erroneamente os nós, ignorando conexões diretas ou indiretas entre eles.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

abstrato

Questões parecidas com resolução

Todas as questões de Algoritmos

🔎 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