1. Você usaria uma lista de adjacência ou uma matriz de adjacência em cada um dos casos abaixo? Justifique sua escolha.
    (a) O grafo tem 10.000 vértices e 20.000 arestas, e é importante usar tão pouco espaço quanto possível.
    (b) O grafo tem 10.000 vértices e 20.000 .000 arestas, e é importante usar tão pouco espaço quanto possível.
    © Você deve ter a aresta adjacente tão rápido quanto possível, sem se importar quanto espaço você usa.

Passo 1

O enunciado pede para escolher entre lista de adjacência ou matriz de adjacência em três cenários, analisando uso de espaço e tempo de acesso. Vamos usar conhecimentos de estruturas de grafos e suas complexidades de memória e de consulta de arestas.

Passo 2

No caso (a), temos um grafo com 10.000 vértices e 20.000 arestas, ou seja, um grafo esparso. A lista de adjacência requer espaço de ordem O(V+E), aqui cerca de 10^4 + 2times10^4, enquanto a matriz exige O(V^2), isto é 10^8 células. Como precisamos economizar espaço, a lista de adjacência é mais eficiente.

Passo 3

No caso (b), o grafo tem 10.000 vértices e 20.000.000 arestas—um grafo denso. A lista usa O(V+E) ≃ 20 milhões de entradas, e a matriz usa O(V^2) ≃ 100 milhões de entradas. Em muitos cenários, uma matriz booleana de 10^8 bits (≈12,5 MB) ocupa menos que estruturas de ponteiros para dezenas de milhões de arestas, portanto a matriz de adjacência é preferível.

Passo 4

No caso ©, o foco é acessar rapidamente se dois vértices são adjacentes, sem se preocupar com espaço. A matriz de adjacência permite teste de adjacência em tempo O(1), enquanto a lista depende do grau do vértice (pior caso O(V)). Logo, usamos matriz de adjacência.

Resposta

(a) Lista de adjacência
(b) Matriz de adjacência
© Matriz de adjacência

Exercícios relacionados