Dado um grafo não direcionado (representado por lista de adjacência) que modela ruas entre bairros, qual…

Questão

Dado um grafo não direcionado (representado por lista de adjacência) que modela ruas entre bairros, qual algoritmo é mais adequado para encontrar o caminho com o menor número de arestas entre dois vértices: BFS ou DFS? Indique o algoritmo e explique sucintamente por quê.

1. A) DFS, porque explora profundamente e assim encontra primeiro o destino, garantindo o menor número de arestas.
2. B) Pesquisa gulosa por heurística local, que minimiza arestas examinadas e por isso obtém o menor trajeto.
3. C) DFS com poda de ciclos sempre retorna o caminho com menos arestas, evitando caminhos mais longos.
4. D) BFS. A busca em largura encontra o menor caminho em número de arestas em grafos não ponderados.
5. E) Algoritmo de Prim, pois constrói uma árvore mínima que contém o menor caminho entre dois vértices.

✅ Resposta correta: alternativa D

Resolução passo a passo

1. O problema pede o caminho com menor número de arestas entre dois vértices de um grafo não direcionado e não ponderado (cada rua conta como uma aresta de mesmo custo).
2. A BFS (busca em largura) visita os vértices por níveis: primeiro todos os vizinhos diretos da origem (distância 1), depois os vizinhos desses (distância 2), e assim por diante. Assim, a primeira vez que o destino é alcançado corresponde ao caminho com o menor número de arestas.
3. A DFS (busca em profundidade) segue um ramo até o fim antes de voltar, então encontra um caminho até o destino, mas não necessariamente o mais curto em arestas.
4. Por isso a alternativa D está correta e coincide com o gabarito oficial.
5. A alternativa A está errada porque explorar profundamente não garante encontrar o destino pelo menor caminho; o primeiro caminho achado pela DFS pode ser muito longo.
6. A alternativa B está errada porque a pesquisa gulosa usa heurística e não garante o caminho ótimo em grafos gerais, além de não ser o método padrão para contar arestas.
7. A alternativa C está errada porque a poda de ciclos não corrige a ordem de exploração da DFS, que continua podendo retornar caminhos longos.
8. A alternativa E está errada porque o algoritmo de Prim constrói uma árvore geradora mínima por pesos, e a árvore resultante não fornece necessariamente o menor caminho entre dois vértices.

💡 Dica: Considere as características dos algoritmos BFS e DFS para justificar sua escolha.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…
• Num mapa de ruas de uma cidade (grafo com arestas não negativas), para encontrar o menor caminho entre dois pontos, qual…
• Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
• Para encontrar o menor número de arestas entre dois vértices em um grafo não ponderado, qual algoritmo é mais adequado e…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…

Todas as questões de Programação - Algoritmos clássicos