Hola a todos.
En esta nota, decidí enumerar las principales estructuras de datos utilizadas para almacenar gráficos en informática, y también hablaré sobre un par de estructuras más que de alguna manera "cristalizaron" para mí.
Vamos a empezar. Pero no desde el principio; creo que todos ya sabemos qué es un gráfico y qué son (dirigidos, no dirigidos, ponderados, no ponderados, con o sin múltiples aristas y bucles).
Entonces vamos. ¿Qué opciones de estructuras de datos para “almacenamiento de gráficos” tenemos?
1. Estructuras de datos matriciales
1.1 Matriz de adyacencia. La matriz de adyacencia es una matriz donde los encabezados de filas y columnas corresponden a los números de los vértices del gráfico, y el valor de cada uno de sus elementos a(i,j) está determinado por la presencia o ausencia de aristas entre vértices. i y j (está claro que para un gráfico no dirigido dicha matriz será simétrica, o podemos acordar que almacenamos todos los valores solo por encima de la diagonal principal). Para gráficos no ponderados, a(i,j) se puede establecer por el número de aristas de i a j (si no existe tal arista, entonces a(i,j)= 0), y para gráficos ponderados, también por el peso (peso total) de los bordes mencionados.
1.2 Matriz de incidencia. En este caso, nuestro gráfico también se almacena en una tabla en la que, por regla general, los números de las filas corresponden a los números de sus vértices y los números de las columnas corresponden a aristas previamente numeradas. Si un vértice y una arista son incidentes entre sí, entonces se escribe un valor distinto de cero en la celda correspondiente (para gráficos no dirigidos, se escribe 1 si el vértice y la arista son incidentes, para gráficos orientados - "1" si la arista "sale" del vértice y "-1" si "incluye" en él (es bastante fácil de recordar, porque el signo "menos" también parece estar "incluido" en el número "-1")). Para gráficos ponderados, nuevamente, en lugar de 1 y -1, puede especificar el peso total del borde.
2. Estructuras de datos de enumeración.
2.1 Lista de adyacencia. Bueno, aquí todo parece sencillo. Cada vértice del gráfico puede, en general, asociarse con cualquier estructura de enumeración (lista, vector, matriz, ...), que almacenará los números de todos los vértices adyacentes al dado. Para gráficos dirigidos, agregaremos a dicha lista solo aquellos vértices a los que hay un borde "dirigido" desde un vértice característico. Para gráficos ponderados la implementación será más compleja.
2.2 Lista de costillas. Una estructura de datos bastante popular. La lista de aristas, como nos dice el Capitán Obviedad, es en realidad una lista de aristas de un gráfico, cada una de las cuales está especificada por el vértice inicial y el vértice final (para gráficos no dirigidos el orden no es importante aquí, aunque para la unificación se puede use varias reglas, por ejemplo, especificando los vértices en orden creciente) y peso (solo para gráficos ponderados).
Puede consultar las listas de matrices enumeradas anteriormente con más detalle (y con ilustraciones), por ejemplo, .
2.3 Matriz de adyacencia. No es la estructura más común. En esencia, es una forma de "empaquetar" listas de adyacencia en una estructura de enumeración (matriz, vector). Los primeros n (según el número de vértices del gráfico) elementos de dicha matriz contienen los índices iniciales de la misma matriz, a partir de los cuales todos los vértices adyacentes al dado se escriben en una fila.
Aquí encontré la explicación más comprensible (para mí):
3. Vector de adyacencia y matriz de adyacencia asociativa
Resultó que el autor de estas líneas, al no ser un programador profesional, pero que periódicamente se ocupaba de gráficos, la mayoría de las veces se ocupaba de listas de aristas. De hecho, es conveniente si el gráfico tiene múltiples bucles y aristas. Y así, en el desarrollo de las listas clásicas de aristas, propongo prestar atención a su “desarrollo/rama/modificación/mutación”, a saber: el vector de adyacencia y la matriz de adyacencia asociativa.
3.1 Vector de adyacencia
Caso (a1): gráfico no ponderado
Llamaremos vector de adyacencia para un gráfico no ponderado un conjunto ordenado de un número par de enteros (a[2i], a[2i+1],..., donde i se numera c 0), en el que cada par de números es a[2i], a[2i+1] especifica un borde del gráfico entre los vértices a[2i] y a[2i+1], respectivamente.
Este formato de grabación no contiene información sobre si el gráfico está dirigido (ambas opciones son posibles). Cuando se utiliza el formato de dígrafo, se considera que el borde está dirigido desde a[2i] a a[2i+1]. Aquí y abajo: para gráficos no dirigidos, si es necesario, se pueden aplicar requisitos para el orden de registro de los vértices (por ejemplo, que el vértice con el valor más bajo del número asignado esté primero).
En C++, es recomendable especificar un vector de adyacencia usando std::vector, de ahí el nombre de esta estructura de datos.
Caso (a2): gráfico no ponderado, los pesos de los bordes son enteros
Por analogía con el caso (a1), llamamos al vector de adyacencia para un gráfico ponderado con pesos de borde enteros un conjunto ordenado (matriz dinámica) de números (a[3i], a[3i+1], a[3i+2], ..., donde i se numera c 0), donde cada “triplete” de números a[3i], a[3i+1], a[3i+2] especifica un borde del gráfico entre los vértices numerados a[3i] y a[3i+1], respectivamente, y el valor a [3i+2] es el peso de esta arista. Un gráfico de este tipo también puede ser dirigido o no.
Caso (b): gráfico no ponderado, ponderaciones de aristas no enteras
Dado que es imposible almacenar elementos heterogéneos en una matriz (vector), por ejemplo, es posible la siguiente implementación. El gráfico se almacena en un par de vectores, en el que el primer vector es el vector de adyacencia del gráfico sin especificar los pesos, y el segundo vector contiene los pesos correspondientes (posible implementación para C++: std::pair ). Así, para una arista definida por un par de vértices bajo los índices 2i, 2i+1 del primer vector, el peso será igual al elemento bajo el índice i del segundo vector.
Bueno, ¿por qué es esto necesario?
Pues bien, al autor de estas líneas le resultó bastante útil para resolver una serie de problemas. Pues bien, desde un punto de vista formal, existirán las siguientes ventajas:
- El vector de adyacencia, como cualquier otra estructura "enumerativa", es bastante compacto, ocupa menos memoria que la matriz de adyacencia (para gráficos dispersos) y es relativamente fácil de implementar.
- Los vértices del gráfico, en principio, también se pueden marcar con números negativos. ¿Qué pasa si tal “perversión” es necesaria?
- Los gráficos pueden contener múltiples aristas y múltiples bucles, con diferentes pesos (positivo, negativo e incluso cero). Aquí no hay restricciones.
- También puedes asignar diferentes propiedades a los bordes, pero para más información al respecto, consulta la sección 4.
Sin embargo, hay que admitir que esta “lista” no implica un acceso rápido al borde. Y aquí viene al rescate la matriz de adyacencia asociativa, que se analiza a continuación.
3.2 Matriz de adyacencia asociativa
Entonces, si el acceso a un borde específico, su peso y otras propiedades es crítico para nosotros, y los requisitos de memoria no nos permiten usar la matriz de adyacencia, entonces pensemos en cómo podemos cambiar el vector de adyacencia para resolver este problema. Entonces, la clave es un borde del gráfico, que se puede especificar como un par ordenado de números enteros. A qué se parece esto? ¿No es una clave en una matriz asociativa? Y, si es así, ¿por qué no lo implementamos? Tengamos una matriz asociativa donde cada clave (un par ordenado de números enteros) se asociará con un valor (un número entero o un número real que especifica el peso del borde). En C++, es recomendable implementar esta estructura basada en el contenedor std::map (std::map , int> o std::mapa , double>), o std::multimap si se esperan múltiples bordes. Bueno, tenemos una estructura para almacenar gráficos que ocupa menos memoria que las estructuras "matriciales", puede definir gráficos con múltiples bucles y aristas y ni siquiera tiene requisitos estrictos para la no negatividad de los números de vértice (no lo sé). quién necesita esto, pero aún así).
4. Las estructuras de datos están llenas, pero falta algo.
Y es cierto: al resolver una serie de problemas, es posible que necesitemos asignar algunas características a los bordes del gráfico y, en consecuencia, almacenarlas. Si es posible reducir inequívocamente estas características a números enteros, entonces es posible almacenar dichos "gráficos con características adicionales" utilizando versiones extendidas del vector de adyacencia y la matriz de adyacencia asociativa.
Entonces, tengamos un gráfico no ponderado, para cada borde del cual es necesario almacenar, por ejemplo, 2 características adicionales especificadas por números enteros. En este caso, es posible definir su vector de adyacencia como un conjunto ordenado no de “pares”, sino de “cuartetos” de números enteros (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , donde a[2i+2] y a[2i+3] determinarán las características de la arista correspondiente. Para un gráfico con pesos enteros de aristas, el orden es generalmente similar (la única diferencia será que los atributos seguirán el peso de la arista y serán especificados por los elementos a[2i+3] y a[2i+4] , y el borde en sí se especificará no 4, sino 5 números ordenados). Y para un gráfico con pesos de borde no enteros, las características se pueden escribir en su componente no ponderado.
Cuando se utiliza una matriz de adyacencia asociativa para gráficos con pesos de arista enteros, es posible especificar como valor no un solo número, sino una matriz (vector) de números que especifican, además del peso de una arista, todos sus demás valores necesarios. características. Al mismo tiempo, un inconveniente para el caso de pesos no enteros será la necesidad de especificar un signo con un número de coma flotante (sí, esto es un inconveniente, pero si no hay tantos signos de este tipo y si no No los configures como dobles demasiado “complicados”, entonces puede que no sea nada). Esto significa que en C++ las matrices de adyacencia asociativa extendida se pueden definir de la siguiente manera: std::map , std::vector> o std::map , std::vector, en el que el primer valor en el “vector clave-valor” será el peso del borde, y luego se ubican las designaciones numéricas de sus características.
Literatura:
Acerca de gráficos y algoritmos en general:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmos: construcción y análisis, 2ª edición: Trans. De inglés – M.: Editorial Williams, 2011.
2. Harari Frank. Teoría de grafos. M.: Mir, 1973.
El informe del autor sobre estos mismos vectores y conjuntos asociativos de adyacencias:
3. Chernoukhov S.A. Vector de adyacencia y matriz de adyacencia asociativa como formas de representar y almacenar gráficos / SA Chernouhov. Vector de adyacencia y mapa de adyacencia como estructuras de datos para representar un gráfico // Colección de artículos de la Conferencia Científica y Práctica Internacional “Problemas de implementar los resultados de desarrollos innovadores y formas de resolverlos” (Saratov, 14.09.2019 de septiembre de 2019). – Sterlitamak: AMI, 65, pág. 69-XNUMX
Fuentes útiles en línea sobre el tema:
4.
5.
Fuente: habr.com