Ola a todos.
Nesta nota, decidín enumerar as principais estruturas de datos utilizadas para almacenar gráficos en informática, e tamén falarei dun par de estruturas deste tipo que dalgún xeito "cristalizaron" para min.
Entón, imos comezar. Pero non desde o principio: creo que todos xa sabemos o que é un gráfico e cales son (dirixido, non dirixido, ponderado, sen ponderar, con ou sen múltiples bordos e bucles).
Entón, imos. Que opcións de estruturas de datos para o "almacenamento de gráficos" temos?
1. Estruturas de datos matriciales
1.1 Matriz de adxacencia. A matriz de adxacencia é unha matriz onde os títulos de fila e columna corresponden aos números dos vértices do gráfico, e o valor de cada un dos seus elementos a(i,j) está determinado pola presenza ou ausencia de arestas entre os vértices. i e j (está claro que para un gráfico non dirixido tal matriz será simétrica, ou podemos aceptar que almacenamos todos os valores só por riba da diagonal principal). Para os gráficos non ponderados, a(i,j) pódese establecer polo número de arestas de i a j (se non existe tal aresta, entón a(i,j)= 0), e para os gráficos ponderados, tamén polo peso (peso total) dos bordes mencionados.
1.2 Matriz de incidencia. Neste caso, o noso gráfico tamén se almacena nunha táboa na que, por regra xeral, os números de fila corresponden aos números dos seus vértices e os números de columna corresponden a bordos prenumerados. Se un vértice e unha aresta son incidentes entre si, entón escríbese un valor distinto de cero na cela correspondente (para gráficos non dirixidos, escríbese 1 se o vértice e a aresta son incidentes, para os gráficos orientados - "1" se o bordo "sae" do vértice e "-1" se "inclúe" nel (é doado de lembrar, porque o signo "menos" tamén parece estar "incluído" no número "-1")). Para os gráficos ponderados, de novo, en lugar de 1 e -1, pode especificar o peso total da aresta.
2. Estruturas de datos de enumeración
2.1 Lista de adxacencia. Ben, todo parece ser sinxelo aquí. Cada vértice do gráfico pode, en xeral, asociarse con calquera estrutura de enumeración (lista, vector, matriz,...), que almacenará os números de todos os vértices adxacentes ao dado. Para os gráficos dirixidos, engadiremos a esa lista só aqueles vértices aos que hai unha aresta "dirixida" a partir dun vértice de características. Para os gráficos ponderados a implementación será máis complexa.
2.2 Lista de costelas. Unha estrutura de datos bastante popular. A lista de arestas, como nos di Captain Obviousness, é en realidade unha lista de bordos do gráfico, cada un dos cales está especificado polo vértice de inicio, o vértice final (para gráficos non dirixidos a orde non é importante aquí, aínda que para a unificación pódese use varias regras, por exemplo, especificando os vértices en orde crecente) e peso (só para gráficos ponderados).
Podes consultar as listas de matriz listadas anteriormente con máis detalle (e con ilustracións), por exemplo, .
2.3 Matriz de adxacencia. Non é a estrutura máis común. No seu núcleo, é unha forma de "empaquetar" listas de adxacencia nunha estrutura de enumeración (matriz, vector). Os primeiros n (segundo o número de vértices do gráfico) elementos dunha matriz deste tipo conteñen os índices iniciais da mesma matriz, a partir dos cales todos os vértices adxacentes ao dado están escritos nunha fila.
Aquí atopei a explicación máis comprensible (para min):
3. Vector de adxacencia e matriz de adxacencia asociativa
Resultou que o autor destas liñas, non sendo un programador profesional, senón que se ocupaba periodicamente de gráficos, a maioría das veces trataba de listas de bordos. De feito, é conveniente se o gráfico ten varios bucles e arestas. E así, no desenvolvemento das listas clásicas de bordos, propoño prestar atención ao seu “desenvolvemento/rama/modificación/mutación”, a saber: o vector de adxacencia e a matriz de adxacencia asociativa.
3.1 Vector de adxacencia
Caso (a1): gráfico non ponderado
Chamaremos un vector de adxacencia para un gráfico non ponderado a un conxunto ordenado dun número par de números enteiros (a[2i], a[2i+1],..., onde i está numerado c 0), no que cada par de números é a[2i], a[2i+1 ] especifica un bordo gráfico entre os vértices a[2i] e a[2i+1], respectivamente.
Este formato de gravación non contén información sobre se o gráfico está dirixido (as dúas opcións son posibles). Cando se utiliza o formato dígrafo, considérase que a aresta está dirixida de a[2i] a a[2i+1]. Aquí e abaixo: para os gráficos non dirixidos, se é necesario, pódense aplicar requisitos para a orde de gravación dos vértices (por exemplo, que o vértice co valor máis baixo do número asignado sexa primeiro).
En C++, é recomendable especificar un vector de adxacencia usando std::vector, de aí o nome desta estrutura de datos.
Caso (a2): gráfico non ponderado, os pesos dos bordos son enteiros
Por analoxía co caso (a1), chamamos ao vector de adxacencia dun gráfico ponderado con pesos de bordo enteiro un conxunto ordenado (matriz dinámica) de números (a[3i], a[3i+1], a[3i+2], ..., onde i está numerado c 0), onde cada "triplete" dos números a[3i], a[3i+1], a[3i+2] especifica un bordo da gráfica entre os vértices numerados a[3i] e a[3i+1], respectivamente, e o valor a [3i+2] é o peso desta aresta. Tal gráfica tamén pode ser dirixida ou non.
Caso (b): gráfico non ponderado, pesos dos bordos non enteiros
Dado que é imposible almacenar elementos heteroxéneos nunha matriz (vector), por exemplo, é posible a seguinte implementación. O gráfico gárdase nun par de vectores, nos que o primeiro vector é o vector de adxacencia do gráfico sen especificar os pesos, e o segundo vector contén os pesos correspondentes (posible implementación para C++: std::pair). ). Así, para unha aresta definida por un par de vértices baixo os índices 2i, 2i+1 do primeiro vector, o peso será igual ao elemento baixo o índice i do segundo vector.
Ben, por que é necesario isto?
Ben, o autor destas liñas considerouno bastante útil para resolver unha serie de problemas. Ben, desde o punto de vista formal, haberá as seguintes vantaxes:
- O vector de adxacencia, como calquera outra estrutura "enumerativa", é bastante compacto, ocupa menos memoria que a matriz de adxacencia (para gráficos escasos) e é relativamente fácil de implementar.
- Os vértices da gráfica, en principio, tamén se poden marcar con números negativos. E se é necesaria esa "perversión"?
- Os gráficos poden conter varias arestas e múltiples bucles, con diferentes pesos (positivo, negativo, incluso cero). Non hai restricións aquí.
- Tamén pode asignar diferentes propiedades aos bordos, pero para obter máis información, consulte a sección 4.
Non obstante, hai que admitir que esta "lista" non implica un acceso rápido ao bordo. E aquí a matriz de adxacencia asociativa vén ao rescate, que se comenta a continuación.
3.2 Matriz de adxacencia asociativa
Entón, se o acceso a un bordo específico, o seu peso e outras propiedades son críticos para nós, e os requisitos de memoria non nos permiten usar a matriz de adxacencia, entón pensemos como podemos cambiar o vector de adxacencia para resolver este problema. Entón, a clave é un bordo do gráfico, que se pode especificar como un par ordenado de números enteiros. Que aspecto ten isto? Non é unha chave nunha matriz asociativa? E, se é así, por que non o implementamos? Teñamos unha matriz asociativa onde cada clave -un par ordenado de enteiros- estará asociada cun valor -un enteiro ou un número real que especifique o peso da aresta. En C++, é recomendable implementar esta estrutura baseada no contedor std::map (std::map , int> ou std::map , double>), ou std::multimap se se esperan varias arestas. Ben, temos unha estrutura para almacenar gráficos que ocupa menos memoria que as estruturas de “matriz”, pode definir gráficos con múltiples bucles e arestas e nin sequera ten requisitos estritos para a non negatividade dos números de vértices (non o sei). quen precisa isto, pero aínda así).
4. As estruturas de datos están cheas, pero falta algo
E é certo: ao resolver unha serie de problemas, é posible que teñamos que asignar algunhas características aos bordos da gráfica e, en consecuencia, almacenalas. Se é posible reducir sen ambigüidades estas características a números enteiros, entón é posible almacenar tales "gráficos con características adicionais" usando versións ampliadas do vector de adxacencia e da matriz de adxacencia asociativa.
Entón, imos ter un gráfico non ponderado, para cada bordo do cal é necesario almacenar, por exemplo, 2 características adicionais especificadas por números enteiros. Neste caso, é posible definir o seu vector de adxacencia como un conxunto ordenado non de “pares”, senón de “cuartetos” de números enteiros (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , onde a[2i+2] e a[2i+3] determinarán as características da aresta correspondente. Para un gráfico con pesos enteiros de arestas, a orde é xeralmente similar (a única diferenza será que os atributos seguirán o peso da aresta e serán especificados polos elementos a[2i+3] e a[2i+4] , e a propia aresta especificarase non 4, senón 5 números ordenados). E para un gráfico con pesos de bordo non enteiros, as características pódense escribir na súa compoñente non ponderada.
Cando se usa unha matriz de adxacencia asociativa para gráficos con pesos de bordo enteiro, é posible especificar como valor non un só número, senón unha matriz (vector) de números que especifiquen, ademais do peso dunha aresta, todos os demais necesarios. características. Ao mesmo tempo, un inconveniente para o caso de pesos non enteiros será a necesidade de especificar un signo cun número de coma flotante (si, isto é un inconveniente, pero se non hai tantos signos deste tipo e se non non os estableza demasiado "complicado" dobre, entón pode que non sexa nada). Isto significa que en C++ as matrices de adxacencia asociativa estendida pódense definir do seguinte xeito: std::map , std::vector> ou std::map , std::vector, no que o primeiro valor do "key-value-vector" será o peso da aresta, e despois sitúanse as designacións numéricas das súas características.
Literatura:
Sobre os gráficos e os algoritmos en xeral:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmos: construción e análise, 2a edición: Trans. do inglés – M.: Editorial Williams, 2011.
2. Harari Frank. Teoría de grafos. M.: Mir, 1973.
Informe do autor sobre estes mesmos vectores e matrices asociativas de adxacencias:
3. Chernoukhov S.A. Vector de adxacencia e matriz de adxacencia asociativa como formas de representar e almacenar gráficos / SA Chernouhov. Vector de adxacencia e mapa de adxacencia como estruturas de datos para representar un gráfico // Colección de artigos da Conferencia Científica e Práctica Internacional "Problemas de implementación dos resultados de desenvolvementos innovadores e formas de resolvelos" (Saratov, 14.09.2019 de setembro de 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Fontes en liña útiles sobre o tema:
4.
5.
Fonte: www.habr.com