Questão 769201

• Banca: CESPE / CEBRASPE
• Órgão: Banco da Amazônia
• Ano: 2012
• Provas: CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Grafos

Julgue os itens seguintes, relativos a grafos.


A implementação de um grafo do tipo ponderado e direcionado na forma de uma matriz de adjacência utiliza menor quantidade de memória que a implementação desse mesmo grafo na forma de uma lista encadeada.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• A representação com uma matriz de adjacência para um grafo com n vértices deverá ter n² elementos, pois cada elemento pode se ligar a qualquer vértice (inclusive ele próprio). Uma lista encadeada vai depender da implementação, mas caso os elementos da lista sejam os vértices, temos que ela terá, na pior das hipóteses (grafo completo), n² elementos.
• Um grafo representado pela lista encadeada (lista de adjacencia) ocupa menos memoria do que a representação do mesmo grafo por uma matriz de adjacencia, pq na 1a. representação (por lista de adjacência) não são representados os vertices não adjacentes (os zeros existentes na matriz de adjacencia).
• Neste site uma explicação sobre grafos ponderados: http://tiagomadeira.com/2006/01/grafos-ponderados/

• Um grafo com N arestas quando representado pela estrutura de dados matriz de adjacencia, ocupa N x N  posicoes no espaço, ja pela representacao de lista de adjacencia ocuparia um vetor com N posicoes e X posicoes os vizinhos de um vertice, representando as arestas.

  Para um grafo completo, existe uma aresta entre quaisquer pares de vertices, a memoria ocupada pela matriz adjacencia e pela lista de adjacencia são iguais.

• Força Guerreiro!!!!!!