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
- Dado um grafo não direcionado (representado por lista de adjacência) que modela ruas entre bairros, qual algoritmo é…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
- Num mapa de ruas de uma cidade (grafo com arestas não negativas), para encontrar o menor caminho entre dois pontos, qual…
- Explique como um algoritmo pode ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo. Utilize…
- Elabore um algoritmo em pseudocódigo que, dado um grafo representado por lista de adjacência e dois vértices (origem…
- Desenvolva um algoritmo que encontre o caminho mais curto em um grafo representando uma rede de computadores. Descreva…
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