- 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.
(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
, aqui cerca de
, enquanto a matriz exige
, isto é
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
≃ 20 milhões de entradas, e a matriz usa
≃ 100 milhões de entradas. Em muitos cenários, uma matriz booleana de
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
, enquanto a lista depende do grau do vértice (pior caso
). Logo, usamos matriz de adjacência.
Resposta
(a) Lista de adjacência
(b) Matriz de adjacência
© Matriz de adjacência
(b) Matriz de adjacência
© Matriz de adjacência