Representación gráfica grande en C++

Question

Puede haber preguntas similares, pero todavía tengo algunas partes que no pude descifrar. Estoy tratando de representar un gráfico no dirigido sin pesos, pero solo para conectado y para no conectado. Intento representar un gráfico (leyendo de un archivo) que tiene 80500 nodos y más de 5.5 millones de bordes. Me preguntaba;

1. Va a ser un gran impacto si cambio mi matriz de adyacencia (la que estoy usando actualmente) a una lista de adyacencia. No tengo ningún problema con la implementación solo preguntando ¿vale la pena el tiempo para convertirlo a la lista?
2. Como acabo de almacenar y hay un tipo de datos especial no store this. Estoy usando y creo que un tipo de datos byte ahorraría mucho tiempo.
3. Cualquier otra estructura que no sea una matriz de adyacencia o lista que podría ser mejor para este problema típico?

Answer 1

Las listas de adyacencia son muchísimo mejor en cuanto a espacio. Porque entonces solo necesitas guardar 5.5 millones * 2 números = 11 000 000 enteros. Suponiendo que guarde enteros cortos (2 bytes), necesita 22 000 000 bytes.

Si lo representa usando una matriz de adyacencia, entonces necesita guardar 80500 * 80500 = 6 480 250 000 elementos. Incluso si los guarda como bytes, tener 22 millones de bytes es mucho mejor que tener más de 6 mil millones de ellos.

EDITAR: Si guarda eges como dos enteros de 4 bytes, entonces tiene 44 000 000 bytes. Si guarda la matriz de manera muy eficiente con el toque de bits, puede guardar 8 elementos en un byte. Pero significa que aún necesita tener 810 031 250 bytes. No es esa gran diferencia ahora, pero sigue siendo 20 veces más.

Answer 2

Si sus datos no son escasos, es posible que no obtenga el mismo ahorro de espacio con una lista de adyacencia. Puede usar una matriz de adyacencia con filas o columnas comprimidas o codificadas, pero su gráfica no está dirigida, de modo que la compresión de filas es probablemente más natural para las búsquedas. Con la compresión, reducirá el espacio, al costo de tiempo de descomprimir filas en la búsqueda.