Olá a todos.
Neste artigo, decidi listar as principais estruturas de dados usadas para armazenar gráficos na ciência da computação, além de comentar algumas outras estruturas que de alguma forma se "cristalizaram" para mim.
Então, vamos começar. Mas não do começo – acredito que todos já sabemos o que é um gráfico e que tipos existem (orientados, não orientados, ponderados, não ponderados, com múltiplas arestas e laços ou sem eles).
Assim, vamos lá. Quais 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 cujos cabeçalhos de linhas e colunas correspondem aos números dos vértices do gráfico, e o valor de cada elemento 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 orientado, essa matriz será simétrica, ou podemos concordar que todos os valores são armazenados apenas acima da diagonal principal). Para gráficos não ponderados, a(i,j) pode ser definido pela quantidade de arestas de i para j (se não existir tal aresta, então a(i,j) = 0), e para os 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, onde geralmente os números das linhas correspondem aos números de seus vértices, e os números das colunas correspondem às arestas previamente enumeradas. Se um vértice e uma aresta são incidentes, é registrado um valor não nulo na célula correspondente (para gráficos não orientados, é registrado 1 no caso de incidência do vértice e da aresta, para os orientados – "1", se a aresta "sai" do vértice e "-1", se ela "entra" nele (é fácil lembrar, pois o sinal "menos" também "entra" no número "-1")). Para gráficos ponderados, novamente, em vez de 1 e -1, podemos indicar o peso total da aresta.
2. Estruturas de dados enumerativas
2.1 Lista de adjacência. Aqui, pelo que parece, tudo é simples. A cada vértice do grafo pode-se, em geral, associar qualquer estrutura enumerativa (lista, vetor, array, …), na qual serão armazenados os números de todos os vértices adjacentes ao dado. Para grafos direcionados, vamos adicionar a essa lista apenas aqueles vértices que possuem uma aresta "direcionada" do vértice de origem. Para grafos ponderados, a implementação será mais complexa.
2.2 Lista de arestas. Uma estrutura de dados bastante popular. A lista de arestas, como nos alerta o Capitão Obvio, consiste na própria lista de arestas do grafo, cada uma das quais é definida por um vértice inicial, um vértice final (para grafos não direcionados, a ordem não importa, embora para unificação possam ser utilizadas diversas regras, por exemplo, listar os vértices em ordem crescente) e um peso (apenas para grafos ponderados).
Sobre as listas-matrizes mencionadas acima, pode-se ver mais detalhes (e ilustrações) em, por exemplo, .
2.3 Array de adjacência. Não é uma estrutura muito comum. Em essência, representa uma forma de "embalagem" das listas de adjacência em uma única estrutura enumerativa (array, vetor). Os primeiros n (de acordo com o número de vértices do grafo) elementos desse array contêm os índices iniciais do mesmo array, a partir dos quais estão sequencialmente registrados todos os vértices adjacentes ao dado.
Aqui encontrei a explicação mais clara (para mim):
3. Vetor de adjacência e Array associativo de adjacência
Acontece que o autor destas linhas, não sendo um programador profissional, mas tendo lidado periodicamente com grafos, na maioria das vezes lidou com listas de arestas. Realmente, é conveniente se há múltiplos laços e arestas em um grafo. Assim, em continuidade às listas de arestas clássicas, proponho prestar atenção em seu "desdobramento/ramificação/modificação/mutação", nomeadamente: vetor de adjacência e array associativo de adjacência.
3.1 Vetor de adjacência
Caso (a1): grafo não ponderado
Chamaremos de vetor de adjacência para um grafo não ponderado um conjunto ordenado de quantidade par de números inteiros (a[2i], a[2i+1],…, onde i é numerado a partir de 0), no qual cada par de números a[2i], a[2i+1] define uma aresta entre os vértices a[2i] e a[2i+1], respectivamente.
Este formato de registro não contém informações sobre se o gráfico é direcionado (ambas as opções são possíveis). Ao utilizar o formato para um gráfico dirigido, considera-se que a aresta é direcionada de a[2i] para a[2i+1]. Aqui e adiante: para gráficos não direcionados, quando necessário, podem ser aplicados requisitos quanto à ordem de registro dos vértices (por exemplo, para que o vértice com o menor valor atribuído apareça primeiro).
Em C++, o vetor de adjacência é razoavelmente definido usando std::vector, e por isso foi escolhido o nome dessa estrutura de dados.
Caso (a2): gráfico não ponderado, pesos das arestas são inteiros
Por analogia com o caso (a1), chamaremos de vetor de adjacência para um gráfico ponderado com pesos inteiros um conjunto ordenado (array dinâmico) de números (a[3i], a[3i+1], a[3i+2],…, onde i é numerado a partir de 0), onde cada "triplo" de números a[3i], a[3i+1], a[3i+2] define uma aresta do gráfico entre os vértices de números a[3i] e a[3i+1], respectivamente, sendo que o valor a[3i+2] é o peso desta aresta. Tal gráfico pode ser tanto direcionado quanto não direcionado.
Caso (b): gráfico não ponderado, pesos das arestas não são inteiros
Dado que em um único array (vetor) não é possível armazenar elementos heterogêneos, por exemplo, a seguinte implementação é possível. O gráfico é armazenado em um par de vetores, no qual o primeiro vetor é o vetor de adjacência do gráfico sem a indicação de pesos, e o segundo vetor contém os pesos correspondentes (implementação possível para C++: std::pair). Assim, para a aresta definida pelo par de vértices nos índices 2i, 2i+1 do primeiro vetor, o peso será igual ao elemento no índice i do segundo vetor.
Mas qual é a necessidade disso?
Bem, para o autor destas linhas, isso pareceu bastante útil para resolver uma série de problemas. E, sob um ponto de vista formal, haverá as seguintes vantagens:
- O vetor de adjacência, assim como qualquer outra estrutura 'enumerativa', é bastante compacto, ocupa menos memória do que a matriz de adjacência (para gráficos esparsos) e é relativamente simples de implementar.
- Os vértices de um gráfico, em princípio, podem ser marcados com números negativos. Caso precise desse 'excesso'.
- Os gráficos podem conter múltiplas arestas e laços, e ainda por cima com pesos diferentes (positivos, negativos, até mesmo zero). Não há nenhuma limitação nesse aspecto.
- Além disso, é possível atribuir diferentes propriedades às arestas - mas veja o item 4.
Contudo, é preciso reconhecer que o acesso rápido à aresta não é o que esta "lista" sugere. E aqui, o Array Associativo de Adjacência surge como uma solução, conforme será explicado a seguir.
3.2 Array Associativo de Adjacência
Assim, se o acesso a uma aresta específica, seu peso e outras propriedades são críticos para nós, e as restrições de memória não permitem o uso de uma matriz de adjacência, vamos considerar como podemos modificar o vetor de adjacência para resolver essa questão. Portanto, a chave é a aresta do grafo, que pode ser representada como um par ordenado de números inteiros. A que se parece? Seria a chave em um array associativo? E, se sim, por que não implementar isso? Vamos ter um array associativo onde cada chave - um par ordenado de números inteiros - será associada a um valor - um número inteiro ou decimal que representa o peso da aresta. Em C++, essa estrutura pode ser implementada com o container std::map (std::map<std::pair, int> ou std::map<std::pair, double>), ou std::multimap, caso se esperem múltiplas arestas. E assim, temos uma estrutura para armazenar grafos que ocupa menos memória do que as estruturas matriciais, pode representar grafos com múltiplos laços e arestas, e nem apresenta exigências rígidas quanto à não negatividade dos números dos vértices (não sei quem precisa disso, mas ainda assim).
4. Estruturas de Dados: Por mais que sejam abundantes, ainda falta algo
E é verdade: ao resolver uma série de problemas, pode surgir a necessidade de atribuir certas características às arestas do grafo e, consequentemente, armazená-las. Se for possível reduzir essas características a números inteiros de forma única, então é viável armazenar esses "grafos com características adicionais" usando versões expandidas do vetor de adjacência e do array associativo de adjacência.
Portanto, suponha que temos um grafo não ponderado, para o qual precisamos armazenar, por exemplo, 2 atributos adicionais, definidos por números inteiros. Nesse caso, podemos definir seu vetor de adjacência como um conjunto ordenado de "quatuplos" de inteiros (a[2i], a[2i+1], a[2i+2], a[2i+3]…), onde a[2i+2] e a[2i+3] definirão os atributos da aresta correspondente. Para um grafo com pesos inteiros nas arestas, a ordem, em geral, é semelhante (a diferença é que os atributos virão após o peso da aresta e serão definidos pelos elementos a[2i+3] e a[2i+4], e a própria aresta será definida por 5 números ordenados, em vez de 4). Para um grafo com pesos não inteiros nas arestas, os atributos poderão ser registrados em seu componente não ponderado.
Ao usar um array associativo de adjacência para grafos com pesos inteiros nas arestas, é possível definir como valor não apenas um número único, mas um array (vetor) de números que definem, além do peso da aresta, todos os outros atributos necessários. Um inconveniente no caso de pesos não inteiros é a necessidade de definir um atributo como um número de ponto flutuante (sim, isso é um inconveniente, mas se houver poucos desses atributos e se não forem definidos como doubles muito "complexos", pode não ser um problema). Assim, em C++, arrays associativos de adjacência podem ser definidos da seguinte forma: std::map <std::pair < int, int>, std::vector> ou std::map <std::pair < int, int>, std::vector, onde o primeiro valor no "vetor-valor-por-chave" será o peso da aresta, e os outros valores serão as representações numéricas de seus atributos.
Literatura:
Sobre grafos e algoritmos em geral:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmos: construção e análise, 2ª edição: Trad. do inglês – Moscovo: Editora Williams, 2011.
2. Harari, Frank. Teoria dos Grafos. Moscovo: Mir, 1973.
Relatório do autor sobre o vetor e o array associativo de adjacência:
3. Chernouhov S.A. Vetor de adjacência e mapa de adjacência como formas de representar e armazenar grafos / S.A. Chernouhov. Vetor de adjacência e mapa de adjacência como estruturas de dados para representar um grafo // Coletânea de artigos da Conferência Científico-Prática Internacional "Problemas da Implementação dos Resultados das Inovações e Caminhos para suas Soluções" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, p. 65-69
Fontes úteis na internet sobre o tema:
4.
5.
Fonte: habr.com
