Hola a todos.
En esta nota, decidí enumerar las principales estructuras de datos utilizadas para almacenar grafos en informática, así como hablaré de un par más de estas estructuras que, de alguna manera, se "cristalizaron" por sí solas.
Entonces, comencemos. Pero no desde el principio; creo que todos sabemos qué es un grafo y qué tipos hay (dirigidos, no dirigidos, ponderados, no ponderados, con aristas múltiples y bucles o sin ellos).
Así que vamos. ¿Qué opciones de estructuras de datos para el "almacenamiento de grafos" tenemos?
1. Estructuras de datos matriciales
1.1 Matriz de adyacencia. La matriz de adyacencia se presenta como una matriz en la que los encabezados de las filas y columnas corresponden a los números de los vértices del grafo, y el valor de cada elemento a(i,j) se determina por la presencia o ausencia de aristas entre los vértices i y j (es claro que para un grafo no dirigido, esta matriz será simétrica, o se puede acordar que todos los valores se almacenan solo por encima de la diagonal principal). Para grafos no ponderados, a(i,j) se puede definir como la cantidad de aristas de i a j (si no hay tal arista, entonces a(i,j) = 0), y para los ponderados, también – como el peso (peso total) de las aristas mencionadas.
1.2 Matriz de incidencia. En este caso, nuestro grafo también se almacena en una tabla, en la cual, por lo general, los números de las filas corresponden a los números de sus vértices y los números de las columnas a las aristas previamente numeradas. Si un vértice y una arista son incidentes entre sí, se registra un valor no nulo en la celda correspondiente (para grafos no dirigidos se registra 1 en caso de incidentia entre el vértice y la arista; para grafos dirigidos, se registra "1" si la arista "sale" del vértice y "-1" si "entra" en él (se recuerda fácilmente, ya que el signo "menos" también "entra" en el número "-1"). Para los grafos ponderados, nuevamente en lugar de 1 y -1 se puede indicar el peso total de la arista.
2. Estructuras de datos enumerativas
2.1 Lista de adyacencia. Aquí, aparentemente, todo es simple. A cada vértice del gráfico se le puede, en términos generales, asociar cualquier estructura enumerativa (lista, vector, arreglo, …), en la que se almacenarán los números de todos los vértices adyacentes a este. Para grafos dirigidos, solo se incluirán en esta lista aquellos vértices a los que haya una arista 'dirigida' desde el vértice de referencia. Para grafos ponderados, la implementación será más compleja.
2.2 Lista de aristas. Una estructura de datos bastante popular. La lista de aristas, como nos indica el Capitán Obvio, es en realidad una lista de las aristas del gráfico, cada una de las cuales se define por un vértice de inicio, un vértice final (en el caso de grafos no dirigidos, el orden no importa, aunque para la unificación se pueden utilizar diferentes reglas, por ejemplo, listar los vértices en orden ascendente) y un peso (solo para grafos ponderados).
Se puede ver más sobre las listas-matriz mencionadas anteriormente (y con ilustraciones), por ejemplo, .
2.3 Arreglo de adyacencia. No es una estructura muy común. Por su naturaleza, representa una forma de 'empaquetar' listas de adyacencia en una única estructura enumerativa (arreglo, vector). Los primeros n (según el número de vértices en el gráfico) elementos de este arreglo contienen los índices iniciales del mismo, a partir de los cuales se listan consecutivamente todos los vértices adyacentes.
Aquí encontré la explicación más comprensible (para mí):
3. Vector de adyacencia y Matriz asociativa de adyacencia
Así sucedió que el autor de estas líneas, no siendo un programador profesional, pero habiendo tratado periódicamente con grafos, la mayoría de las veces ha tratado con listas de aristas. De hecho, es conveniente si hay bucles múltiples y aristas en el gráfico. Y así, en el desarrollo de las clásicas listas de aristas, propongo prestar atención también a su 'evolución/ramificación/modificación/mutación', a saber: el vector de adyacencia y la matriz asociativa de adyacencia.
3.1 Vector de adyacencia
Caso (a1): grafo no ponderado
Llamaremos vector de adyacencia para un grafo no ponderado a un conjunto ordenado de un número par de enteros (a[2i], a[2i+1],…, donde i comienza en 0), en el que cada par de números a[2i], a[2i+1] define una arista del gráfico entre los vértices a[2i] y a[2i+1], respectivamente.
Este formato de registro no contiene información sobre si el grafo es dirigido (ambas versiones son posibles). Al usar el formato para un orgrafo, se considera que la arista está dirigida de a[2i] a a[2i+1]. A partir de aquí: para grafos no dirigidos, si es necesario, se pueden aplicar requisitos sobre el orden de los vértices (por ejemplo, para que primero vaya el vértice con el menor valor de su número asignado).
En C++, es conveniente definir el vector de adyacencia utilizando std::vector, de ahí el nombre de esta estructura de datos.
Caso (a2): grafo no ponderado, las aristas tienen pesos enteros.
Por analogía con el caso (a1), llamaremos vector de adyacencia para un grafo ponderado con pesos enteros un conjunto ordenado (arreglo dinámico) de números (a[3i], a[3i+1], a[3i+2],…, donde i se numera desde 0), donde cada 'tripleta' de números a[3i], a[3i+1], a[3i+2] define una arista del grafo entre los vértices con los números a[3i] y a[3i+1] respectivamente, y el valor a[3i+2] es el peso de esta arista. Tal grafo puede ser tanto dirigido como no dirigido.
Caso (b): grafo no ponderado, las aristas tienen pesos no enteros.
Dado que no se pueden almacenar elementos heterogéneos en un mismo arreglo (vector), es posible, por ejemplo, la siguiente implementación. El grafo se almacena en un par de vectores, donde el primer vector es el vector de adyacencia del grafo sin especificar pesos, y el segundo vector contiene los pesos correspondientes (una posible implementación en C++: std::pair). Así, para una arista definida por un par de vértices en los índices 2i, 2i+1 del primer vector, el peso será igual al elemento en el índice i del segundo vector.
¿Y por qué es necesario esto?
Bueno, para el autor de estas líneas, esto ha parecido bastante útil para resolver una serie de problemas. Y, desde un punto de vista formal, aquí habrá ciertas ventajas:
- El vector de adyacencia, al igual que cualquier otra estructura 'enumerativa', es bastante compacto, ocupa menos memoria que la matriz de adyacencia (para grafos dispersos), y es relativamente fácil de implementar.
- Los vértices del grafo, en principio, pueden estar marcados también con números negativos. Tal vez se necesite tal 'excentricidad'.
- Los grafos pueden contener múltiples aristas y múltiples lazos, e incluso con diferentes pesos (positivos, negativos, incluso cero). No hay limitaciones al respecto.
- Además, se pueden asignar diferentes propiedades a las aristas; pero sobre esto, véase el punto 4.
Sin embargo, hay que reconocer que este "listado" no implica un acceso rápido a la arista. Y aquí el arreglo asociativo de adyacencia viene al rescate, como se explicará a continuación.
3.2 Arreglo asociativo de adyacencia
Así que, si el acceso a una arista específica, su peso y otras propiedades es crítico para nosotros, y los requisitos de memoria no nos permiten usar una matriz de adyacencia, pensemos en cómo se puede modificar el vector de adyacencia para resolver esta tarea. Así que, la clave es la arista del grafo, que se puede definir como un par ordenado de números enteros. ¿A qué se parece esto? ¿No es acaso una clave en un arreglo asociativo? Entonces, si es así, ¿por qué no implementarlo? Supongamos que tenemos un arreglo asociativo donde a cada clave—un par ordenado de números enteros—se le asigna un valor—un número entero o real que representa el peso de la arista. En C++, es sensato implementar esta estructura utilizando el contenedor std::map (std::map <std::pair , int> o std::map <std::pair , double>), o std::multimap, si se prevén múltiples aristas. Y así, tenemos una estructura para almacenar grafos, que ocupa menos memoria que las estructuras "matriciales", puede representar grafos con múltiples lazos y aristas e incluso no tiene requisitos estrictos sobre la no negatividad de los números de los vértices (no sé a quién le puede interesar, pero aún así).
4. Estructuras de datos, por mucho que se llenen, aún falta algo
Y es verdad: al resolver una serie de problemas, puede surgir la necesidad de asignar ciertas características a las aristas del grafo y, en consecuencia, de almacenarlas. Si es posible reducir claramente estas características a números enteros, entonces es posible almacenar tales "grafos con características adicionales" utilizando versiones extendidas del vector de adyacencia y del arreglo asociativo de adyacencia.
Entonces, supongamos que tenemos un grafo no ponderado, para el cual necesitamos almacenar, por ejemplo, 2 características adicionales definidas por números enteros para cada arista. En este caso, es posible definir su vector de adyacencia como un conjunto ordenado de no «pares», sino «cuartetos» de números enteros (a[2i], a[2i+1], a[2i+2], a[2i+3]…), donde a[2i+2] y a[2i+3] definirán las características de la arista correspondiente. Para un grafo con pesos enteros en las aristas, el orden es, en general, análogo (la única diferencia será que las características seguirán al peso de la arista y se definirán por los elementos a[2i+3] y a[2i+4], y la arista en sí se definirá no por 4, sino por 5 números ordenados). Para un grafo con pesos no enteros en las aristas, las características se podrán escribir en su componente no ponderado.
Al usar un array asociativo de adyacencia para grafos con pesos enteros en las aristas, es posible definir como valor no un solo número, sino un array (vector) de números que, además del peso de la arista, defina todas sus otras características necesarias. Sin embargo, en el caso de los pesos no enteros, la incomodidad será la necesidad de definir la característica como un número de punto flotante (sí, esto es incómodo, pero si tales características no son muchas y si no se definen como doubles «demasiado complicados», puede que no sea tan problemático). Por lo tanto, en C++, los arrays asociativos de adyacencia extendidos pueden definirse de la siguiente manera: std::map <std::pair , std::vector> o std::map <std::pair , std::vector, donde el primer valor en el «vector-valor-por-clave» será el peso de la arista, seguido de las designaciones numéricas de sus características.
Literatura:
Sobre grafos y algoritmos en general:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmos: diseño y análisis, 2ª edición: Trad. del inglés – Moscú: Editorial Williams, 2011.
2. Harari, Frank. Teoría de grafos. Moscú: Mir, 1973.
Informe del autor sobre este mismo vector y el array asociativo de adyacencia:
3. Chernouhov S.A. Vector de adyacencia y mapa de adyacencia como estructuras de datos para representar un grafo // Recopilación de artículos de la Conferencia Internacional de Ciencia y Práctica "Problemas de implementación de los resultados de desarrollos innovadores y sus soluciones" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, p. 65-69
Fuentes de Internet útiles sobre el tema:
4.
5.
Fuente: habr.com
