¿Cuál es la forma más eficiente en cuanto al espacio para implementar una estructura de datos gráficos?

Por lo general, implemento gráficos como listas doblemente vinculadas, pero esto es bastante ineficiente en mi experiencia ya que necesito k punteros / referencias para k vecinos, por lo que para un gráfico no dirigido tendría ~ 2k enlaces de vecinos dentro de las listas si mis cálculos son correctos. ¿Hay una mejor manera de ahorrar espacio? Sé que algunos de los enlaces pueden hacerse singulares si el gráfico está dirigido, pero ¿hay alguna manera de hacer un mejor trabajo de esto?

Bueno, si lo único que le importa es la eficiencia del espacio, lo mejor sería una estructura de datos comprimidos, pero, por supuesto, esto no es muy eficiente para acceder o actualizar ...

Si su gráfico tiene un número relativamente pequeño de nodos y es bastante denso (digamos que existe al menos el 5% de todas las conexiones posibles), entonces puede encontrar que es más eficiente en el espacio crear una matriz de adyacencia en lugar de usar listas de bordes. Esto requeriría solo un bit por conexión posible (dirigida), y un total de n * n bits donde tiene n nodos.

De lo contrario, si necesita usar enlaces contiguos, entonces no puede hacer mejor que una referencia por enlace, ya que este es el contenido mínimo de información que necesita almacenar. Si desea vínculos de retroceso, necesitará el doble de enlaces.

Hay algunos trucos que puedes probar además de esto. Por ejemplo, podría intentar compartir subconjuntos de enlaces (si A y B se refieren a cada uno de C, D, E, entonces solo almacene la lista de enlaces C, D, E una vez .....). Sin embargo, esto se volverá complejo bastante rápido y dudo que valga la pena el esfuerzo en la mayoría de los casos.

Otro truco: suponiendo que su gráfico tenga un número razonable de nodos, sin duda ahorrará espacio indexando, por ejemplo, utilizando un número de índice de nodo de 16 bits en lugar de un puntero / referencia completo.

Dependerá de la estructura de sus datos.

Para un gráfico denso con bordes no dirigidos, realmente no se puede superar una lista de matrices de bits que representan una matriz triangular. A List<BitArray>por ejemplo. Lógicamente, se vería así:

 0123
0
11
211
3001
41010

A partir de ahí, puede usar el índice del BitArray raíz para indexar en una lista que almacena los datos de su nodo.

Por ejemplo, obtener todos los vecinos de un nodo sería como:

// C#
List<Node> Nodes = /* populated elsewhere */
List<BitArray> bits = /* populated elsewhere */
public static IEnumerable<Node> GetNeighbours(int x)    
{
    for (int i = 0; i < bits[idx].Count; i++)
    {
        if (this.bits[idx][i])
            yield return this.Nodes[i];
    }

    for (int i = 0; i < this.Nodes.Count; i++)
    {
        if (idx < this.bits[i].Count && this.bits[i][idx])
            yield return this.Nodes[i];
    }    
}

(tenga en cuenta que también puede elegir el tipo de índice, dependiendo de la cantidad de datos, para que sea un byte o una abreviatura o algo por el estilo, ya que todos los índices serán positivos. No considero que esto sea una microoptimización, ya que es trivial)

Para un gráfico dirigido, seguiría la ruta de un * n conjunto de bits para almacenar la conectividad ... a menos que sea muy escaso en comparación con el número de nodos, donde puede ir a una lista de índices de adyacencia.