Para encontrar o menor número de arestas entre dois vértices em um grafo não ponderado, qual algoritmo é mais…
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
Para encontrar o menor número de arestas entre dois vértices em um grafo não ponderado, qual algoritmo é mais adequado e por quê? (cite o nome do algoritmo e princípio básico).
- A) Algoritmo de Prim — usado para encontrar árvores geradoras mínimas.
- B) BFS pode ser aplicado, mas apenas em grafos orientados.
- C) BFS (Busca em Largura) — explora o grafo em camadas a partir do vértice de origem, garantindo o menor número de arestas até cada vértice.
- D) Algoritmo de Dijkstra — usa pesos para determinar menores caminhos.
- E) DFS (Busca em Profundidade) — ideal para encontrar ciclos em um grafo.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Em um grafo não ponderado, cada aresta tem o mesmo peso implícito (custo 1), então o menor número de arestas entre dois vértices é o mesmo que a menor distância no grafo.
- Para isso, o algoritmo mais adequado é a BFS (Busca em Largura), que visita os vértices em camadas: primeiro os vizinhos diretos da origem (distância 1), depois os vizinhos desses (distância 2), e assim por diante.
- Como a BFS só alcança um vértice novo depois de todos os vértices de camada anterior, a primeira vez que encontra um vértice é garantidamente pelo caminho com menos arestas.
- A alternativa C descreve exatamente esse princípio, o que confirma o gabarito.
- A alternativa A está errada, pois o algoritmo de Prim serve para construir árvores geradoras mínimas, não para menores caminhos entre dois vértices.
- A alternativa B está errada, pois a BFS funciona tanto em grafos orientados quanto em não orientados; restringi-la a orientados é falso.
- A alternativa D está errada, pois o Dijkstra é voltado a grafos ponderados e, embora funcione sem pesos, é um algoritmo mais geral e desnecessário aqui.
- A alternativa E está errada, pois a DFS (Busca em Profundidade) não garante o menor número de arestas, já que segue um caminho até o fim antes de recuar; além disso, ela é usada para detectar ciclos, não para menores caminhos.
💡 Dica: Identifique o algoritmo e explique seu princípio básico.
Alternativa por alternativa
O aluno associa 'menor caminho' a 'árvore geradora mínima' por ter o termo 'mínimo' em comum, sem perceber que Prim minimiza o peso total de uma árvore, não a distância entre dois vértices.
O aluno acredita que a BFS só funciona em grafos orientados, confundindo o sentido das arestas com a própria estrutura de busca, que vale para qualquer grafo.
Por que engana: Confundir o algoritmo de Dijkstra com BFS, acreditando que ambos são adequados para grafos não ponderados.
BFS visita vértices por níveis de distância (em arestas) a partir da origem; ao alcançar o destino pela primeira vez obtém-se o caminho com mínimo de arestas. Complexidade O(V+E).
O aluno pensa que o Dijkstra é a única ou a melhor escolha para menores caminhos, sem notar que, sem pesos, ele é desnecessário e a BFS resolve o problema diretamente.
O aluno acredita que a DFS encontra o menor caminho, confundindo o aprofundar-se no grafo com a busca pela menor distância, e associa a DFS apenas à detecção de ciclos.
Raio-X da questão
menor caminho em grafos
avaliacao
algoritmos de busca em grafos · tipos de grafos
Revisar algoritmos de busca em grafos, como BFS e DFS.
Confundir o algoritmo de Dijkstra com BFS, acreditando que ambos são adequados para grafos não ponderados.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- A professora fez uma tabela: os grupos ficam nas linhas, os dias da semana ficam nas colunas e cada espaço mostra a…
- Um aplicativo percebe quais fotos mostram animais. O que ele pode fazer para achar essas fotos mais rápido? O que o…
- Em Manaus, a escola testa um programa que separa mensagens em urgente e comum. Aplique a ideia de classificacao e…
- Desenhe um grafo que represente uma rota de entregas entre três escolas (E1, E2, E3) e dois pontos de apoio (P1, P2)…
- Um mapa de estações de metrô em que as estações estão ligadas por linhas pode ser representado como um grafo? Escreva a…
- Escolha um exemplo do cotidiano (por exemplo: contatos em um aplicativo da escola ou paradas de ônibus) e descreva como…
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