matriz de adyacencia vs lista de memoria eficiente
Si el gráfico es un gráfico completo que tiene techo propio, creo que la memoria de la matriz de adyacencia es más eficiente que la lista de adyacencia. ¿Es correcto?
En mi opinión, cuando se trata de una matriz dispersa, la lista adyacente ahorra memoria, pero cuando se trata de una matriz de densidad, espero que haya una base concreta para utilizar matrices adyacentes.
Una matriz de adyacencia requiere un bit de almacenamiento por cada borde posible. Esto es óptimo si aproximadamente la mitad de todas las aristas posibles están realmente en el gráfico, porque hay aproximadamente 2 |V| 2 de estas configuraciones.
Si sabes que el gráfico está completo, entonces sólo necesitas almacenar ese hecho, porque te dice exactamente cuál sería la matriz de adyacencia.
Si sabes que el gráfico está casi completo, entonces puedes almacenar, para cada vértice, una lista de vértices que no son sus vecinos, y que será más pequeña que una matriz de adyacencia.
El concepto de cuán compactos se pueden almacenar los datos dependiendo de lo que se sabe sobre ellos (sus estadísticas) se denomina " entropía " en la teoría de la información, ya que es muy similar al concepto del mismo nombre en física.
