Ao projetar um algoritmo para calcular o caminho mais curto entre salas em um mapa da escola, qual…

Questão

Ao projetar um algoritmo para calcular o caminho mais curto entre salas em um mapa da escola, qual representação de grafo facilita buscas eficientes e por quê?

1. A) Matriz de incidência (vértice×aresta) — itera vizinhos rapidamente.
2. B) Grafo representado por lista de adjacência, pois facilita iteração sobre vizinhos e usa menos memória em grafos esparsos.
3. C) Árvore binária de vértices para acelerar buscas de caminhos.
4. D) Lista de arestas (edge list) — percorre só as arestas do vértice eficientemente.
5. E) Matriz de adjacência — usa V×V e é ideal para grafos esparsos.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. O problema pede a representação de grafo que facilita buscas eficientes de caminho mais curto (como Dijkstra ou BFS) em um mapa, onde salas são vértices e corredores são arestas.
2. Algoritmos de caminho mínimo precisam, a cada passo, descobrir rapidamente os vizinhos de um vértice. A lista de adjacência armazena, para cada vértice, apenas a lista dos vértices ligados a ele, então essa iteração é direta e proporcional ao número de vizinhos.
3. Em um mapa escolar, o número de corredores é pequeno em relação ao número de pares possíveis de salas, ou seja, o grafo é esparso. Nesse caso a lista de adjacência usa memória proporcional a V+E, enquanto a matriz de adjacência usa V×V, com muitas posições vazias.
4. Comparando com o gabarito oficial, a alternativa B está correta e eu concordo com ele.
5. A alternativa A está errada porque a matriz de incidência tem dimensão V×E e, para descobrir vizinhos, é preciso percorrer uma coluna inteira de arestas, o que não é rápido.
6. A alternativa C está errada porque uma árvore binária é um tipo específico de grafo sem ciclos com estrutura de filhos fixos, não uma representação geral de um mapa com corredores em qualquer padrão.
7. A alternativa D está errada porque a lista de arestas guarda apenas pares de vértices, sem organização por vértice, e para achar os vizinhos de uma sala seria preciso varrer todas as arestas.
8. A alternativa E está errada porque a matriz de adjacência é ineficiente para grafos esparsos, pois ocupa V×V posições independentemente da quantidade real de corredores; ela é mais indicada para grafos densos.

💡 Dica: Considere as propriedades dos grafos e suas aplicações em algoritmos de busca.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Em um jogo, cada sala é representada por um ponto. Os corredores ligam as salas, e uma sala pode ter vários corredores…
• Considere um problema que envolve a otimização de rotas entre várias cidades. Qual estrutura é mais eficiente para…
• Descreva como representar um labirinto como um grafo e escreva um algoritmo em linguagem descritiva que encontre o…
• Ao representar um autômato de estados com muitos estados e poucas transições entre eles (grafo esparso) para executar um…
• Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
• Em um aplicativo de mapas, cada cidade será representada por um ponto. As estradas ligarão esses pontos, e uma cidade…

Todas as questões de Programação - Programação usando grafos e árvores