Se em um grafo, cada aresta conecta duas cidades e queremos pesquisar a conexão entre São Paulo e Rio de…
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
Se em um grafo, cada aresta conecta duas cidades e queremos pesquisar a conexão entre São Paulo e Rio de Janeiro. Que método utilizar?
- A) Busca em largura (BFS)
- B) Busca em profundidade (DFS)
- C) Algoritmo de Dijkstra
- D) Busca binária
- E) Ordenação Topológica
✅ Resposta correta: alternativa A
Resolução passo a passo
- Identifique o problema. Temos um grafo em que cada aresta liga duas cidades, e queremos saber se existe conexão entre São Paulo e Rio de Janeiro. O enunciado não menciona pesos nas arestas, então cada ligação conta como um passo de mesmo custo.
- Escolha a ferramenta adequada. Para descobrir se há caminho entre dois vértices em um grafo sem pesos, e com a vantagem de encontrar o caminho com o menor número de conexões, o método clássico é a busca em largura (BFS). Ela visita primeiro os vizinhos do vértice inicial, depois os vizinhos dos vizinhos, e assim por diante, por níveis.
- Por que a BFS é a melhor resposta. Como ela explora o grafo por camadas, a primeira vez que alcança Rio de Janeiro a partir de São Paulo corresponde ao caminho com menos arestas. Isso responde à pergunta de conexão de forma eficiente e direta.
- Por que as outras alternativas não são a melhor escolha. A busca em profundidade (B) também descobre se existe conexão, mas não garante o caminho mais curto, o que a torna menos adequada à ideia de conexão mais direta. O algoritmo de Dijkstra (C) é voltado a grafos com pesos nas arestas, que não aparecem aqui. A busca binária (D) exige dados ordenados em um vetor e não se aplica a grafos. A ordenação topológica (E) serve para ordenar vértices de grafos direcionados acíclicos, não para encontrar conexão entre duas cidades.
- Observação sobre o gabarito. O gabarito A está coerente com a interpretação mais comum da questão. A DFS poderia ser aceita como alternativa válida para apenas verificar existência de conexão, mas a BFS é a resposta esperada por fornecer o caminho mais curto em grafos sem peso.
💡 Dica: Considere os métodos de busca em grafos.
Alternativa por alternativa
Ideal para encontrar o caminho mais curto em um grafo não ponderado.
O aluno acredita que a busca em profundidade é o método padrão para qualquer pesquisa em grafos, pois ela também encontra caminhos entre dois vértices. Ele não percebe que a DFS pode retornar um caminho longo e não o mais curto.
Por que engana: Confundir busca em largura com busca em profundidade, escolhendo DFS para encontrar o caminho mais curto entre cidades.
O aluno associa qualquer problema de caminho em grafos ao algoritmo de Dijkstra, sem verificar se as arestas têm pesos. Ele ignora que, sem pesos, o caminho mais curto é obtido com a BFS.
O aluno pensa que a busca binária serve para procurar qualquer item, inclusive uma conexão entre cidades, por ser um método de busca famoso. Ele não lembra que ela exige dados ordenados em uma estrutura linear.
O aluno confunde a palavra ordenação, presente no nome do método, com a ideia de encontrar uma sequência entre cidades. Ele não sabe que a ordenação topológica se aplica a grafos direcionados acíclicos e tem outro objetivo.
Raio-X da questão
métodos de busca em grafos
avaliacao
conceito de grafos · busca em largura e profundidade
Revisar os métodos de busca em grafos, como busca em profundidade e busca em largura.
Confundir busca em largura com busca em profundidade, escolhendo DFS para encontrar o caminho mais curto entre cidades.
pensamento_critico
cotidiano
Questões parecidas com resolução
- Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
- A partir de um grafo que representa cidades como vértices e as estradas como arestas, qual informação pode ser extraída?
- Identifique qual estrutura de dados é mais adequada para representar um grafo que conecta cidades. Considere a relação…
- Uma equipe de mobilidade urbana está desenvolvendo um aplicativo para planejar viagens entre cidades brasileiras. Cada…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…
- Em um projeto de cidade inteligente, você precisa interligar diversos serviços públicos. Que método de grafo poderia ser…
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