Uso de memória da matriz e lista

showMemoryUse()

O método exibe a quantidade de memória usada pela matriz de adjacência e pela lista de adjacência.
O cálculo do uso de memória é o seguinte:

• Para a matriz
  
  
  
  • É pego a quantidade de nós da matriz e elevado ao quadrado. O resultado é multiplicado por 4 (tamanho de inteiros, em bytes)
    
  • qtdnos*qtdnos*4
    
  
  
• Para a lista
  
  
  
  • Primeiro se é multiplicado a quantidade de nós por 4. Isso é para calcular o tamanho do vetor que armazenará as listas encadeadas.
    
  • O resultado da multiplicação da quantidade de nós por 4 é somado com a quantidade de arestas multiplicada por 12. Isso por que cada elemento da lista (que é, na verdade, uma aresta) armazena um peso e o indice do nó para onde se tem a ligação, ambos inteiros (tamanho 4 bytes) e um ponteiro para o próximo elemento, sendo que o ponteiro utiliza também 4 bytes.
    
  • (qtdnos*4) + (qtdarestas * 12);
    
  
  
  

Realizando alguns testes, observamos que a lista de adjacência só é eficiente caso seja usada para representar uma matriz esparsa. Matrizes não-esparsas ainda são eficientes, na questão de uso de memoria, na forma de matrizes de adjacência.

Exemplo

Levando em consideração um grafo de 100 nós, o uso da matriz de adjacência é de 40000 bytes. A lista de adjacência, por sua vez, usa apenas 400 bytes se não houver arestas. Se preenchermos o grafo com 10000 arestas, fazendo todos os nós se conectarem, o uso de memória da matriz permanece inalterado enquanto o uso de memória da lista sobe para 120400 bytes.

  void Grafo::showMemoryUse()
  {
      int mem_matr;
      int mem_list;
      mem_matr = qtdnos*qtdnos*4;
      mem_list = (qtdnos*4) + (qtdarestas * 12);
      cout << "Memória usada pela matriz: " << mem_matr << endl;
      cout << "Memória usada pela lista: " << mem_list << endl;
  }