Qual a estrutura ideal para armazenar as conexões de um grafo direcionado?
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
Qual a estrutura ideal para armazenar as conexões de um grafo direcionado?
- A) Matriz de adjacência
- B) Lista encadeada
- C) Vetor
- D) Fila
- E) Pilha
✅ Resposta correta: alternativa A
Resolução passo a passo
- Um grafo direcionado é formado por vértices e arcos, em que cada conexão tem um sentido (de origem para destino). A questão pergunta qual estrutura armazena essas conexões de forma ideal. Passo 2: A matriz de adjacência é uma matriz n x n, em que a posição (i, j) indica se existe um arco do vértice i para o vértice j. Como a matriz não é simétrica, ela registra naturalmente o sentido de cada conexão, o que a torna a representação clássica e mais direta para grafos direcionados, com consulta de existência de arco em tempo constante. Passo 3: A lista encadeada (lista de adjacência) também representa grafos direcionados e costuma economizar memória em grafos esparsos; por isso é uma alternativa forte e, em muitos contextos práticos, preferível. No entanto, a questão fala em estrutura ideal de forma geral e, entre as opções, a matriz de adjacência é a representação canônica para armazenar as conexões. Passo 4: O vetor é uma estrutura linear que não representa relações entre vértices por si só, então não serve para guardar conexões de forma direta. Passo 5: A fila é uma estrutura de acesso FIFO usada para processar elementos em ordem de chegada, como em percursos em largura, mas não armazena as conexões do grafo. Passo 6: A pilha é uma estrutura LIFO usada em percursos em profundidade e na recursão, também sem função de armazenar conexões. Passo 7: Conclusão: a alternativa A está correta e coincide com o gabarito oficial, com a ressalva de que a lista encadeada é uma escolha válida e eficiente para grafos esparsos.
💡 Dica: Considere as características das estruturas de dados.
Alternativa por alternativa
Esta estrutura permite representar bem as conexões entre os vértices em um grafo direcionado.
Acredita que a lista encadeada é sempre a melhor estrutura por economizar memória, sem considerar que a questão busca a representação clássica das conexões e que a matriz oferece consulta direta de arcos.
Por que engana: Confundir estruturas lineares como listas ou vetores com estruturas específicas para representar grafos, como a matriz de adjacência.
Imagina que, por ser a estrutura mais simples, o vetor basta para guardar as conexões, sem perceber que ele não representa relações entre dois vértices.
Confunde a estrutura usada para percorrer o grafo (como na busca em largura) com a estrutura que armazena suas conexões.
Associa a pilha aos algoritmos de percurso em profundidade e supõe que ela também guarda as arestas ou arcos do grafo, quando ela apenas controla a ordem de visita.
Raio-X da questão
estruturas de dados
avaliacao
conceito de grafo direcionado · matriz de adjacencia
Revisar as estruturas de dados utilizadas em grafos.
Confundir estruturas lineares como listas ou vetores com estruturas específicas para representar grafos, como a matriz de adjacência.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas de…
- Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
- Qual das seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
- Qual estrutura de dados é mais indicada para representar um grafo em um programa?
- Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas arestas?
- Considere um grafo não direcionado representando amigos. Qual a representação mais adequada para armazená-lo?
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