Olá a todos.
Nesta nota, decidi listar as principais estruturas de dados usadas para armazenar gráficos na ciência da computação, e também falarei sobre mais algumas dessas estruturas que de alguma forma “cristalizaram” para mim.
Então, vamos começar. Mas não desde o início - acho que todos nós já sabemos o que é um gráfico e o que eles são (direcionado, não direcionado, ponderado, não ponderado, com ou sem múltiplas arestas e loops).
Então vamos. Que opções de estruturas de dados para “armazenamento de gráficos” temos?
1. Estruturas de dados matriciais
1.1 Matriz de adjacência. A matriz de adjacência é uma matriz onde os títulos das linhas e colunas correspondem aos números dos vértices do gráfico, e o valor de cada um de seus elementos a(i,j) é determinado pela presença ou ausência de arestas entre os vértices i e j (é claro que para um gráfico não direcionado tal matriz será simétrica, ou podemos concordar que armazenamos todos os valores apenas acima da diagonal principal). Para gráficos não ponderados, a(i,j) pode ser definido pelo número de arestas de i a j (se não existir tal aresta, então a(i,j)= 0), e para gráficos ponderados, também pelo peso (peso total) das arestas mencionadas.
1.2 Matriz de incidência. Nesse caso, nosso gráfico também é armazenado em uma tabela na qual, via de regra, os números das linhas correspondem aos números de seus vértices, e os números das colunas correspondem às arestas pré-numeradas. Se um vértice e uma aresta são incidentes um ao outro, então um valor diferente de zero é escrito na célula correspondente (para gráficos não direcionados, 1 é escrito se o vértice e a aresta são incidentes, para gráficos orientados - “1” se a aresta “sai” do vértice e “-1” se “inclui” nele (é fácil de lembrar, porque o sinal “menos” também parece estar “incluído” no número “-1”)). Para gráficos ponderados, novamente, em vez de 1 e -1, você pode especificar o peso total da aresta.
2. Estruturas de dados de enumeração
2.1 Lista de adjacências. Bem, tudo parece simples aqui. Cada vértice do grafo pode, em geral, ser associado a qualquer estrutura de enumeração (lista, vetor, array, ...), que armazenará os números de todos os vértices adjacentes ao dado. Para gráficos direcionados, adicionaremos a essa lista apenas aqueles vértices para os quais existe uma aresta “direcionada” de um vértice de recurso. Para gráficos ponderados a implementação será mais complexa.
2.2 Lista de costelas. Uma estrutura de dados bastante popular. A lista de arestas, como nos diz o Capitão Obviedade, é na verdade uma lista de arestas do grafo, cada uma das quais é especificada pelo vértice inicial, pelo vértice final (para grafos não direcionados a ordem não é importante aqui, embora para unificação você possa use várias regras, por exemplo, especificando os vértices em ordem crescente) e peso (somente para gráficos ponderados).
Você pode ver as listas de matrizes listadas acima com mais detalhes (e com ilustrações), por exemplo, .
2.3 Matriz de adjacência. Não é a estrutura mais comum. Em sua essência, é uma forma de “empacotar” listas de adjacências em uma estrutura de enumeração (matriz, vetor). Os primeiros n (de acordo com o número de vértices do gráfico) elementos de tal array contêm os índices iniciais do mesmo array, a partir dos quais todos os vértices adjacentes ao dado são escritos em uma linha.
Aqui encontrei a explicação mais compreensível (para mim):
3. Vetor de Adjacência e Matriz de Adjacência Associativa
Descobriu-se que o autor dessas linhas, não sendo um programador profissional, mas que lidava periodicamente com gráficos, na maioria das vezes lidava com listas de arestas. Na verdade, é conveniente se o gráfico tiver vários loops e arestas. E assim, no desenvolvimento das listas clássicas de arestas, proponho prestar atenção ao seu “desenvolvimento/ramificação/modificação/mutação”, a saber: o vetor de adjacência e a matriz de adjacência associativa.
3.1 Vetor de adjacência
Caso (a1): gráfico não ponderado
Chamaremos um vetor de adjacência para um gráfico não ponderado de um conjunto ordenado de um número par de inteiros (a[2i], a[2i+1],..., onde i é numerado c 0), em que cada par de números é a[2i], a[2i+1 ] especifica uma aresta do gráfico entre os vértices a[2i] e a[2i+1], respectivamente.
Este formato de gravação não contém informações sobre se o gráfico está direcionado (ambas as opções são possíveis). Ao usar o formato de dígrafo, a aresta é considerada direcionada de a[2i] para a[2i+1]. Aqui e abaixo: para gráficos não direcionados, se necessário, podem ser aplicados requisitos para a ordem de registro dos vértices (por exemplo, que o vértice com o menor valor do número atribuído a ele venha primeiro).
Em C++, é aconselhável especificar um vetor de adjacência usando std::vector, daí o nome desta estrutura de dados.
Caso (a2): gráfico não ponderado, os pesos das arestas são inteiros
Por analogia com o caso (a1), chamamos o vetor de adjacência para um gráfico ponderado com pesos de aresta inteiros de um conjunto ordenado (matriz dinâmica) de números (a[3i], a[3i+1], a[3i+2], ..., onde i é numerado c 0), onde cada “tripleto” de números a[3i], a[3i+1], a[3i+2] especifica uma aresta do gráfico entre vértices numerados a[3i] e a[3i+1], respectivamente, e o valor a [3i+2] é o peso desta aresta. Esse gráfico também pode ser direcionado ou não.
Caso (b): gráfico não ponderado, pesos de arestas não inteiros
Como é impossível armazenar elementos heterogêneos em um array (vetor), por exemplo, a seguinte implementação é possível. O gráfico é armazenado em um par de vetores, em que o primeiro vetor é o vetor de adjacência do gráfico sem especificar os pesos, e o segundo vetor contém os pesos correspondentes (possível implementação para C++: std::pair ). Assim, para uma aresta definida por um par de vértices sob os índices 2i, 2i+1 do primeiro vetor, o peso será igual ao elemento sob o índice i do segundo vetor.
Bem, por que isso é necessário?
Pois bem, o autor destas linhas achou-o bastante útil para resolver uma série de problemas. Pois bem, do ponto de vista formal, haverá as seguintes vantagens:
- O vetor de adjacência, como qualquer outra estrutura “enumerativa”, é bastante compacto, ocupa menos memória que a matriz de adjacência (para grafos esparsos) e é relativamente fácil de implementar.
- Os vértices do gráfico, em princípio, também podem ser marcados com números negativos. E se tal “perversão” for necessária?
- Os gráficos podem conter múltiplas arestas e múltiplos loops, com pesos diferentes (positivo, negativo e até zero). Não há restrições aqui.
- Você também pode atribuir propriedades diferentes às arestas - mas para saber mais sobre isso, consulte a seção 4.
Contudo, há que admitir que esta “lista” não implica um acesso rápido à borda. E aqui o Matriz de Adjacência Associativa vem em socorro, que é discutido abaixo.
3.2 Matriz de adjacência associativa
Portanto, se o acesso a uma aresta específica, seu peso e outras propriedades são críticos para nós, e os requisitos de memória não nos permitem usar a matriz de adjacência, então vamos pensar em como podemos alterar o vetor de adjacência para resolver esse problema. Portanto, a chave é uma aresta do gráfico, que pode ser especificada como um par ordenado de inteiros. O que isso parece? Não é uma chave em uma matriz associativa? E, em caso afirmativo, por que não o implementamos? Tenhamos um array associativo onde cada chave - um par ordenado de inteiros - será associada a um valor - um inteiro ou um número real que especifica o peso da aresta. Em C++, é aconselhável implementar esta estrutura com base no contêiner std::map (std::map , int> ou std::map , double>) ou std::multimap se forem esperadas múltiplas arestas. Bem, temos uma estrutura para armazenar gráficos que ocupa menos memória que estruturas “matriciais”, pode definir gráficos com múltiplos loops e arestas e nem sequer possui requisitos rígidos para a não negatividade dos números de vértices (não sei quem precisa disso, mas ainda assim).
4. As estruturas de dados estão cheias, mas falta algo
E é verdade: ao resolver uma série de problemas, podemos precisar atribuir algumas características às arestas do gráfico e, consequentemente, armazená-las. Se for possível reduzir inequivocamente esses recursos a números inteiros, então é possível armazenar esses “gráficos com recursos adicionais” usando versões estendidas do vetor de adjacência e da matriz de adjacência associativa.
Então, tenhamos um gráfico não ponderado, para cada aresta do qual é necessário armazenar, por exemplo, 2 características adicionais especificadas por inteiros. Neste caso, é possível definir seu vetor de adjacência como um conjunto ordenado não de “pares”, mas de “quartetos” de inteiros (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , onde a[2i+2] e a[2i+3] determinarão as características da aresta correspondente. Para um grafo com pesos inteiros de arestas, a ordem geralmente é semelhante (a única diferença será que os atributos seguirão o peso da aresta e serão especificados pelos elementos a[2i+3] e a[2i+4] , e a própria aresta será especificada não 4, mas 5 números ordenados). E para um gráfico com pesos de aresta não inteiros, os recursos podem ser escritos em seu componente não ponderado.
Ao usar uma matriz de adjacência associativa para grafos com pesos de aresta inteiros, é possível especificar como valor não um único número, mas uma matriz (vetor) de números que especifica, além do peso de uma aresta, todos os outros necessários. características. Ao mesmo tempo, um inconveniente para o caso de pesos não inteiros será a necessidade de especificar um sinal com um número de ponto flutuante (sim, isso é um inconveniente, mas se não houver tantos sinais desse tipo, e se você não não os configure muito “complicados” em dobro, então pode não ser nada). Isso significa que em C++ matrizes de adjacência associativa estendida podem ser definidas da seguinte forma: std::map , std::vector> ou std::map , std::vector, em que o primeiro valor do “vetor-valor-chave” será o peso da aresta, e a seguir serão localizadas as designações numéricas de suas características.
Literatura:
Sobre gráficos e algoritmos em geral:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmos: construção e análise, 2ª edição: Trad. do inglês – M.: Editora Williams, 2011.
2. Harari Frank. Teoria dos grafos. M.: Mundo, 1973.
O relatório do autor sobre esse mesmo vetor e matriz associativa de adjacências:
3. Chernoukhov S.A. Vetor de adjacência e matriz de adjacência associativa como formas de representar e armazenar gráficos / SA Chernouhov. Vetor de adjacência e mapa de adjacência como estruturas de dados para representar um gráfico // Coleção de artigos da Conferência Científica e Prática Internacional “Problemas de implementação dos resultados de desenvolvimentos inovadores e formas de resolvê-los” (Saratov, 14.09.2019 de setembro de 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Fontes online úteis sobre o assunto:
4.
5.
Fonte: habr.com