Estructuras de datos para el almacenamiento de gráficos: una revisión de las existentes y dos "casi nuevas"

Hola a todos

En esta nota, decidí enumerar las principales estructuras de datos utilizadas para almacenar gráficos en ciencias de la computación, y también hablar sobre un par de otras estructuras que de alguna manera cristalizaron.

Entonces comencemos. Pero no desde el principio: creo que es un gráfico y cuáles son (orientado, no orientado, ponderado, no ponderado, con múltiples bordes y bucles o sin ellos), todos ya lo sabemos.

Entonces vamos. ¿Cuáles son las opciones de estructuras de datos para el "almacenamiento de gráficos" que tenemos?

1. Estructuras de datos matriciales

1.1 Matriz de adyacencia. La matriz de adyacencia es una matriz donde los encabezados de fila y columna 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 bordes entre los vértices i y j (está claro que dicha matriz para un gráfico no dirigido será simétrico, bueno, o puede aceptar que almacenemos todos los valores solo por encima de la diagonal principal). Para gráficos no ponderados, se puede especificar a (i, j) por el número de aristas de i a j (si no existe dicho borde, entonces a (i, j) = 0), y para los ponderados, por el peso (peso total) de los bordes mencionados.

1.2 La matriz de incidencia. En este caso, nuestro gráfico también se almacena en una tabla, en la cual, como regla, los números de fila corresponden a los números de sus vértices, y los números de columna corresponden a bordes numerados previamente. Si el vértice y el borde son incidentes entre sí, entonces se escribe un valor distinto de cero en la celda correspondiente (para gráficos no dirigidos, 1 se escribe en el caso de incidencia del vértice y borde, para gráficos orientados "1" si el borde "sale" del vértice y "-1" si "entra" (se recuerda con bastante facilidad, 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. Enumeración de estructuras de datos

2.1 lista de adyacencia. Bueno, todo parece ser simple. En general, cada vértice de un gráfico puede asociarse con cualquier estructura de enumeración (lista, vector, matriz, ...), en la que se almacenarán los números de todos los vértices adyacentes a este. Para gráficos orientados, solo enumeraremos los vértices en los que hay un borde "dirigido" desde el atributo de vértice. Para gráficos ponderados, la implementación será más compleja.

2.2 Lista de costillas. Estructura de datos bastante popular. La lista de bordes, como nos dice el Capitán Evidence, es en realidad una lista de bordes del gráfico, cada uno de los cuales está definido por un vértice inicial, un vértice final (para gráficos no dirigidos, el orden no es importante aquí, aunque se pueden usar diferentes reglas para la unificación, por ejemplo, especificar vértices en orden ascendente) y peso (solo para gráficos ponderados).

Sobre las listas de matrices enumeradas anteriormente, puede ver (por ejemplo, aquí ) con más detalle.

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 (por el número de vértices del gráfico) de dicha matriz contienen índices iniciales de la misma matriz, a partir de los cuales todos los vértices adyacentes a esta se escriben en una fila.

Aquí encontré la explicación más comprensible (para mí): ejuo.livejournal.com/4518.html

3. Vector de adyacencia y matriz de adyacencia asociativa

Sucedió de modo que el autor de estas líneas, no siendo un programador profesional, sino que lidiando periódicamente con gráficos, a menudo trataba con listas de bordes. De hecho, es conveniente si el gráfico tiene múltiples bucles y aristas. Y ahora, en el desarrollo de las listas clásicas de bordes, propongo prestar atención a su "desarrollo / ramificación / modificación / mutación", a saber: el vector de adyacencia y el conjunto asociativo de adyacencia.

3.1 Vector de adyacencia

Caso (A1): recuento no ponderado

Llamaremos al 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 está numerado c 0), en el que cada par de números a [2i], a [2i +1] define el 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á orientado (ambas opciones son posibles). Cuando se utiliza el formato de dígrafo, se supone que el borde se dirige de un [2i] a un [2i + 1]. De aquí en adelante: para gráficos no dirigidos, si es necesario, se pueden aplicar los requisitos para el orden de registro de vértices (por ejemplo, para que el vértice con el valor más bajo del número asignado sea el primero).

En C ++, es recomendable especificar el vector de adyacencia usando std :: vector, del cual se eligió el nombre de esta estructura de datos.

Caso (a2): gráfico no ponderado, pesos de bordes enteros

Por analogía con el caso (a1), llamamos al vector de adyacencia para un gráfico ponderado con pesos de borde entero un conjunto ordenado (matriz dinámica) de números (a [3i], a [3i + 1], a [3i + 2], ..., donde i está numerado c 0), donde cada "triplete" de los números a [3i], a [3i + 1], a [3i + 2] define el borde de la gráfica entre los vértices debajo de los números a [3i] y a [3i + 1], respectivamente, y El valor de a [3i + 2] es el peso de este borde. Tal gráfico también puede ser orientado o no.

Caso (b): gráfico no ponderado, pesos de borde no enteros

Como los elementos heterogéneos no pueden almacenarse en una matriz (vector), es posible la siguiente implementación, por ejemplo. 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 indicar pesos, y el segundo vector contiene los pesos correspondientes (una posible implementación para C ++ es: std :: pair <std :: vector, std :: vector>). Por lo tanto, para un borde definido por un par de vértices debajo de 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?

Bueno, para el autor de estas líneas para resolver una serie de problemas, esto parecía bastante útil. Bueno, desde un punto de vista formal, habrá tales ventajas:

• El vector de adyacencia, como cualquier otra estructura "enumerativa", es lo suficientemente compacto, ocupa menos memoria que la matriz de adyacencia (para gráficos dispersos), es relativamente fácil de implementar.
• Los vértices del gráfico, en principio, se pueden marcar con números negativos. De repente, también se necesita esa "perversión".
• Los gráficos pueden contener múltiples aristas y múltiples bucles, con diferentes pesos (positivo, negativo, incluso cero). No hay restricciones aquí.
• Y a las costillas se les pueden asignar diferentes propiedades, pero sobre esto, vea el párrafo 4.

Sin embargo, debo admitir que este "listot" no implica un acceso rápido a la costilla. Y aquí la matriz de adyacencia asociativa se apresura a ayudar, sobre lo cual, a continuación.

3.2 Matriz de adyacencia asociativa

Entonces, si para nosotros el acceso a un borde en particular, su peso y otras propiedades son críticas, y los requisitos de memoria no permiten el uso de una matriz de adyacencia, entonces pensemos cómo puede cambiar el vector de adyacencia para resolver este problema. Entonces, la clave es el borde del gráfico, que se puede definir como un par ordenado de enteros. ¿Cómo se ve? ¿Podría ser una clave en una matriz asociativa? Y si es así, ¿por qué no implementamos esto? Tengamos una matriz asociativa de este tipo, donde cada clave, un par ordenado de enteros, se asociará con un valor, un entero o un número real que especifica el peso del borde. En C ++, es aconsejable implementar esta estructura sobre la base del contenedor std :: map (std :: map <std :: pair <int, int>, int> o std :: map <std :: pair <int, int>, double>) , o std :: multimap si se suponen múltiples aristas. Bueno, y aquí tenemos una estructura para almacenar gráficos, que ocupa menos memoria que las estructuras de "matriz", puede definir gráficos con múltiples bucles y bordes e incluso sin requisitos estrictos para la no negatividad de los números de vértice (no sé quién lo necesita, pero aun así).

4. Las estructuras de datos al menos "inundan", pero falta algo

Y la verdad es que, al resolver una serie de problemas, es posible que necesitemos asignar algunos atributos a los bordes del gráfico y, en consecuencia, almacenarlos. Si es posible reducir inequívocamente estas características a enteros, entonces es posible almacenar tales "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 signos adicionales especificados por enteros. En este caso, es posible especificar su vector de adyacencia como un conjunto ordenado de no "pares", sino "cuartetos" de enteros (a [2i], a [2i + 1], a [2i + 2], a [2i + 3] .. .), donde un [2i + 2] y un [2i + 3] determinarán las características del borde correspondiente. Para un gráfico con pesos de borde enteros, el orden es generalmente similar (la única diferencia es que los signos siguen el peso del borde y están dados 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, los atributos se pueden escribir en su componente no ponderado.

Cuando se usa una matriz de adyacencia asociativa para gráficos con pesos de borde enteros, es posible especificar no un número individual, sino una matriz (vector) de números que, además del peso de borde, especifique todos sus otros atributos necesarios. En este caso, el inconveniente para el caso de los pesos no enteros será la necesidad de especificar una característica con un número de coma flotante (sí, esto es un inconveniente, pero si no hay tantos signos de este tipo y si no los configura como dobles "difíciles", entonces puede que no sea nada) . Y así, en C ++, las matrices de adyacencia asociativa extendida se pueden definir de la siguiente manera: std :: map <std :: pair <int, int>, std :: vector> o std :: map <std :: pair <int, int>, std :: vector, con el primer valor en "vector-value-by-key" es el peso del borde, y luego se ubican las designaciones numéricas de sus características.

Referencias

Sobre 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: Per. del ingles - M .: Williams Publishing House, 2011.
2. Harari Frank. Teoría de grafos. M .: Mir, 1973.
El informe del autor sobre estos mismos vectores y matriz asociativa de adyacencia:
3. Chernoukhov S.A. Vector de adyacencia y matriz de adyacencia asociativa como formas de representar y almacenar gráficos / SA Chernouhov. El vector de adyacencia y el mapa de adyacencia como estructuras de datos para representar un gráfico // Colección de artículos de la conferencia internacional científica y práctica "Problemas para implementar los resultados de desarrollos innovadores y formas de resolverlos" (Saratov, 14 de septiembre de 2019). - Sterlitamak: AMI, 2019, p. 65-69
Fuentes útiles de Internet sobre el tema:
4.prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html