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

14

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

    
pregunta World Engineer 12.05.2012 - 05:37

2 respuestas

12

Bueno, si lo único que te importa es la eficiencia de espacio, entonces lo mejor sería una estructura de datos comprimidos, pero, por supuesto, esto no es muy eficiente para el acceso o la actualización ...

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 el espacio para crear un matriz de adecuación en lugar de utilizar listas de borde. Esto requeriría solo un bit por conexión posible (dirigida) y n * n bits en total donde tenga n nodos.

De lo contrario, si necesita usar enlaces vecinos, no podrá hacerlo mejor que una referencia por enlace, ya que este es el contenido de información mínima que necesita almacenar. Si desea enlaces 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 almacenará 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: si la gráfica tiene un número razonable de nodos, seguramente ahorrará espacio al indexar, por ejemplo. utilizando un número de índice de nodo de 16 bits en lugar de un puntero completo / referencia.

    
respondido por el mikera 12.05.2012 - 06:17
6

Dependerá de la estructura de tus 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. Un List<BitArray> por ejemplo. Lógicamente, se vería así:

 0123
0
11
211
3001
41010

Desde allí, puede utilizar el índice de la raíz BitArray para indexar en una lista que almacena sus datos de nodo.

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

// 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 ser un byte o ushort o algo en ese sentido, ya que todos los índices serán positivos. No considero que esta sea una microoptimización como es trivial)

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

    
respondido por el Steven Evers 12.05.2012 - 08:16

Lea otras preguntas en las etiquetas