Me estoy preparando para una entrevista de codificación, y estaba refrescando mi mente en los gráficos. Me preguntaba lo siguiente: en todos los lugares que he visto, se supone que las listas de adyacencia son más eficientes en cuanto a la memoria que las matrices de adyacencia para gráficos dispersos grandes y, por lo tanto, deberían preferirse en ese caso. Además, calcular el número de bordes salientes de un nodo requiere O (N) en una matriz mientras que O (1) en una lista, así como cuáles son los nodos adyacentes en O (num nodos adyacentes) para la lista en lugar de O (N) para la matriz.
Tales lugares incluyen el libro de Cormen et al., O StackOverFlow: Size of a graph using adjacency list versus adjacency matrix? o Wikipedia.representación de gráficos: lista de adyacencia frente a la matriz
Sin embargo, usando una representación de matriz dispersa como en la representación de Almacenamiento de Fila Comprimido, el requisito de memoria es solo O (número de no ceros) = O (número de bordes), que es lo mismo que usar listas. El número de bordes salientes de un nodo es O (1) (se almacena directamente en CRS), y los nodos adyacentes se pueden enumerar en O (num nodos adyacentes).
¿Por qué no se discute? ¿Debo suponer que CSR es una especie de representación de la lista de adyacencia del gráfico representado por la matriz? ¿O es el argumento de que las matrices son intensivas en memoria porque no tienen en cuenta las representaciones de matrices dispersas?
Gracias!