Tres formas de almacenar un gráfico en memoria, ventajas y desventajas

Un par de cosas más a considerar:

1. El modelo de matriz se presta más fácilmente a gráficos con bordes ponderados, almacenando los pesos en la matriz. El modelo de objeto / puntero necesitaría almacenar pesos de borde en una matriz paralela, lo que requiere sincronización con la matriz de puntero.

2. El modelo objeto / puntero funciona mejor con gráficos dirigidos que con gráficos no dirigidos porque los punteros tendrían que mantenerse en pares, lo que puede convertirse en no sincronizado.

El método de objetos y punteros sufre de dificultad de búsqueda, como algunos han señalado, pero es bastante natural para hacer cosas como construir árboles de búsqueda binarios, donde hay una gran cantidad de estructura adicional.

Personalmente me encantan las matrices de adyacencia porque hacen todo tipo de problemas mucho más fáciles, utilizando herramientas de la teoría de grafos algebraicos. (La k-ésima potencia de la matriz de adyacencia da el número de caminos de longitud k desde el vértice i al vértice j, por ejemplo. Agregar una matriz de identidad antes de tomar el poder kth para obtener el número de caminos de longitud

Pero todo el mundo dice que las matrices de adyacencia son caras de memoria! Solo tienen la mitad de la razón: Puede sortear esto usando matrices dispersas cuando su gráfico tiene pocas aristas. Las estructuras de datos de matriz dispersas hacen exactamente el trabajo de mantener una lista de adyacencia, pero todavía tienen la gama completa de operaciones de matriz estándar disponibles, dando lo mejor de ambos mundos.

Creo que su primer ejemplo es un poco ambiguo: nodos como objetos y bordes como punteros. Podría realizar un seguimiento de estos almacenando solo un puntero a algún nodo raíz, en cuyo caso acceder a un nodo dado puede ser ineficiente (digamos que desea nodo 4 - si el objeto node no se proporciona, puede que tenga que buscarlo). En este caso, también perdería partes del gráfico que no son accesibles desde el nodo raíz. Creo que este es el caso f64 rainbow está asumiendo cuando dice que la complejidad de tiempo para acceder a un nodo dado es O (n).

De lo contrario, también podría mantener una matriz (o hashmap) llena de punteros a cada nodo. Esto permite a O(1) acceder a un nodo dado, pero aumenta un poco el uso de memoria. Si n es el número de nodos y e es el número de aristas, la complejidad espacial de este enfoque sería O(n + e).

La complejidad del espacio para el enfoque matricial sería a lo largo de las líneas de O(n^2) (suponiendo que las aristas son unidireccionales). Si su gráfico es escaso, tendrá una gran cantidad de vacío células en su matriz. Pero si su gráfico está completamente conectado (e = n^2), esto se compara favorablemente con el primer enfoque. Como dice RG, también puede tener menos errores de caché con este enfoque si asigna la matriz como un trozo de memoria, lo que podría hacer que seguir muchos bordes alrededor del gráfico sea más rápido.

El tercer enfoque es probablemente el más eficiente en espacio para la mayoría de los casos - O(e) - pero haría que encontrar todos los bordes de un nodo dado sea una tarea de O(e). No puedo pensar en un caso donde este sería muy útil.

Echa un vistazo a tabla de comparación en wikipedia. Da una comprensión bastante buena de cuándo usar cada representación de gráficos.

Bien, así que si los bordes no tienen pesos, la matriz puede ser una matriz binaria, y el uso de operadores binarios puede hacer que las cosas van muy, muy rápido en ese caso.

Si el gráfico es escaso, el método objeto/puntero parece mucho más eficiente. Mantener los objetos / punteros en una estructura de datos específicamente para persuadirlos en un solo trozo de memoria también podría ser un buen plan, o cualquier otro método para lograr que permanezcan juntos.

La lista de adyacencia-simplemente una lista de nodos conectados - parece de lejos la memoria más eficiente, pero probablemente también la más lenta.

Invertir un gráfico dirigido es fácil con la representación de la matriz, y fácil con la lista de adyacencia, pero no tan grande con la representación de objeto/puntero.

Hay otra opción: nodos como objetos, bordes como objetos también, cada borde está al mismo tiempo en dos listas doblemente enlazadas: la lista de todos los bordes que salen del mismo nodo y la lista de todos los bordes que entran en el mismo nodo.

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

La sobrecarga de memoria es grande (2 punteros por nodo y 6 punteros por borde) pero obtienes

• O (1) inserción del nodo
• O (1) inserción de bordes (dados punteros a nodos "from" y "to")
• O (1) eliminación de bordes (dada la pointer)
• O(deg(n)) node deletion (dado el puntero)
• O(deg (n)) encontrar vecinos de un nodo

La estructura también puede representar un gráfico bastante general: multigrafo orientado con bucles (es decir, puede tener múltiples bordes distintos entre los mismos dos nodos, incluidos múltiples bucles distintos, bordes que van de x a x).

Una explicación más detallada de este enfoque está disponible aquí.