Estruturas de dados para armazenamento de gráficos: uma revisão das existentes e duas "quase novas"

Olá pessoal.

Nesta nota, decidi listar as principais estruturas de dados usadas para armazenar gráficos em ciência da computação e também falar sobre algumas outras estruturas que de alguma forma se cristalizaram por mim.

Então, vamos começar. Mas não desde o início - acho que o que é um gráfico e o que é (orientado, não orientado, ponderado, não ponderado, com várias arestas e loops ou sem eles), todos nós já sabemos.

Então vamos lá. Quais são as opções para estruturas de dados que temos para "armazenamento de gráficos".

1. Estruturas de dados matriciais

1.1 Matriz de adjacência. A matriz de adjacência é uma matriz em que os títulos de linha e coluna 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 iej (é claro que essa matriz para um gráfico não direcionado será simétrico, ou você pode concordar que armazenamos todos os valores somente acima da diagonal principal). Para gráficos não ponderados, a (i, j) pode ser especificado pelo número de arestas de i a j (se não houver essa aresta, então a (i, j) = 0) e, para os ponderados, pelo peso (peso total) das arestas mencionadas.

1.2 A matriz de incidência. Nesse caso, nosso gráfico também é armazenado em uma tabela na qual, como regra, os números de linhas correspondem aos números de seus vértices e os números das colunas correspondem às arestas pré-numeradas. Se o vértice e a aresta são incidentes um ao outro, um valor diferente de zero é gravado na célula correspondente (para gráficos não direcionados, 1 é gravado no caso de incidência do vértice e aresta, para gráficos orientados "1" se a aresta "sai" do vértice e "-1" se "entra" (é lembrado facilmente, porque o sinal de 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ência. Bem, tudo parece ser simples. Em geral, cada vértice de um gráfico pode ser associado a qualquer estrutura de enumeração (lista, vetor, matriz, ...), na qual os números de todos os vértices adjacentes a este serão armazenados. Para gráficos orientados, listaremos apenas vértices nos quais existe uma aresta "direcionada" do atributo de vértice. Para gráficos ponderados, a implementação será mais complexa.

2.2 Lista de costelas. Estrutura de dados bastante popular. A lista de arestas, como o Capitão Evidence nos diz, é na verdade uma lista de arestas do gráfico, cada uma delas definida por um vértice inicial, um vértice final (para gráficos não direcionados, a ordem não é importante aqui, embora regras diferentes possam ser usadas para a unificação, por exemplo, especifique vértices em ordem). crescente) e peso (apenas para gráficos ponderados).

Sobre as listas de matrizes listadas acima, você pode ver (por exemplo, aqui ) com mais detalhes.

2.3 Matriz de adjacência. Não é a estrutura mais comum. Na sua essência, é uma forma de "empacotar" listas de adjacência em uma estrutura de enumeração (matriz, vetor). Os primeiros n elementos (pelo número de vértices do gráfico) de uma matriz contêm índices iniciais da mesma matriz, a partir dos quais todos os vértices adjacentes a ela são gravados nela em uma linha.

Aqui encontrei a explicação mais compreensível (para mim): ejuo.livejournal.com/4518.html

3. Vetor de adjacência e matriz associativa de adjacência

Aconteceu que o autor dessas linhas, não sendo um programador profissional, mas lidando periodicamente com gráficos, costumava lidar com listas de arestas. De fato, é conveniente se o gráfico tiver vários loops e arestas. E agora, 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 associativa de adjacência.

3.1 Vetor de adjacência

Caso (A1): contagem não ponderada

Vamos chamar o vetor de adjacência para um gráfico não ponderado de um conjunto ordenado de um número par de números inteiros (a [2i], a [2i + 1], ..., onde i é numerado c 0), no qual cada par de números a [2i], a [2i +1] define a 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 a orientação do gráfico (as duas opções são possíveis). Ao usar o formato do dígrafo, supõe-se que a aresta seja direcionada de um [2i] para um [2i + 1]. A seguir: para gráficos não direcionados, se necessário, os requisitos para a ordem dos vértices de gravação podem ser aplicados (por exemplo, para que o vértice com o valor mais baixo do número atribuído a ele vá primeiro).

Em C ++, é aconselhável especificar o vetor de adjacência usando std :: vector, no qual o nome dessa estrutura de dados foi escolhido.

Caso (a2): gráfico não ponderado, pesos de arestas inteiras

Por analogia com o caso (a1), chamamos o vetor de adjacência para um gráfico ponderado com pesos de arestas inteiras um conjunto ordenado (matriz dinâmica) de números (a [3i], [3i + 1], [[3i + 2], ..., onde i é numerado c 0), onde cada "trigêmeo" dos números a [3i], a [3i + 1], a [3i + 2] define a aresta do gráfico entre os vértices sob os números a [3i] e [3i + 1], respectivamente, e o valor de a [3i + 2] é o peso dessa aresta. Esse gráfico também pode ser orientado ou não.

Caso (b): gráfico não ponderado, pesos das arestas não inteiras

Como os elementos heterogêneos não podem ser armazenados em uma matriz (vetor), a seguinte implementação é possível, por exemplo. O gráfico é armazenado em um par de vetores, no qual o primeiro vetor é o vetor de adjacência do gráfico sem indicar pesos e o segundo vetor contém os pesos correspondentes (uma possível implementação para C ++ é: std :: pair <std :: vector, std :: vector>). 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?

Bem, para o autor dessas linhas, por resolver vários problemas, isso parecia bastante útil. Bem, do ponto de vista formal, haverá essas vantagens:

• O vetor de adjacência, como qualquer outra estrutura "enumerativa", é compacto o suficiente, ocupa menos memória que a matriz de adjacência (para gráficos esparsos) e é relativamente fácil de implementar.
• Os vértices do gráfico, em princípio, podem ser marcados com números negativos. De repente, essa "perversão" também é necessária.
• Os gráficos podem conter várias arestas e vários loops, com pesos diferentes (positivo, negativo e até zero). Não há restrições aqui.
• E as costelas podem receber propriedades diferentes - mas, para isso, consulte o parágrafo 4.

No entanto, devo admitir, esse “listot” não implica acesso rápido à costela. E aqui a matriz de adjacência associativa se apressa para ajudar, sobre a qual - abaixo.

3.2 Matriz de adjacência associativa

Portanto, se o acesso a uma borda em particular é crítico, seu peso e outras propriedades são críticos, e os requisitos de memória não permitem o uso de uma matriz de adjacência, vamos pensar em como você pode alterar o vetor de adjacência para resolver esse problema. Portanto, a chave é a borda do gráfico, que pode ser definida como um par ordenado de números inteiros. Como é isso? Poderia ser uma chave em uma matriz associativa? E se sim, por que não implementamos isso? Vamos ter uma matriz associativa em que cada chave - um par ordenado de números inteiros - seja associada a um valor - um número inteiro ou um número real que especifique o peso da aresta. Em C ++, é recomendável implementar essa estrutura com base no contêiner std :: map (std :: map <std :: pair <int, int>, int> ou std :: map <std :: pair <int, int>, double>) ou std :: multimap se várias arestas forem assumidas. Bem, e aqui temos uma estrutura para armazenar gráficos, que ocupa menos memória do que estruturas "matrizes", pode definir gráficos com vários loops e arestas e mesmo sem requisitos estritos para a não-negatividade dos números de vértices (não sei quem precisa, mas ainda).

4. Estruturas de dados pelo menos “inundam”, mas algo está faltando

E a verdade é: ao resolver vários problemas, podemos precisar atribuir alguns atributos às bordas do gráfico e, consequentemente, armazená-los. Se for possível reduzir inequivocamente esses recursos para números inteiros, é possível armazenar esses “gráficos com recursos adicionais” usando versões estendidas do vetor de adjacência e a matriz de adjacência associativa.

Portanto, vamos ter um gráfico não ponderado, para cada extremidade da qual é necessário armazenar, por exemplo, 2 sinais adicionais especificados por números inteiros. Nesse caso, é possível especificar seu vetor de adjacência como um conjunto ordenado de não "pares", mas "quartetos" de números inteiros (a [2i], a [2i + 1], a [2i + 2], a [2i + 3] .. .), onde a [2i + 2] e a [2i + 3] determinam os recursos da aresta correspondente. Para um gráfico com pesos de arestas inteiras, a ordem é geralmente semelhante (a única diferença é que os sinais seguem o peso da aresta e são dados pelos elementos a [2i + 3] e a [2i + 4], e a aresta em si será especificada não 4, mas 5 números ordenados). E para um gráfico com pesos de aresta não inteiros, os atributos podem ser gravados em seu componente não ponderado.

Ao usar uma matriz de adjacência associativa para gráficos com pesos de arestas inteiras, é possível especificar não um número individual, mas uma matriz (vetor) de números que, além do peso da aresta, especifica todos os outros atributos necessários. Ao mesmo tempo, o inconveniente para o caso de pesos não inteiros será a necessidade de especificar um caractere com um número de ponto flutuante (sim, isso é um inconveniente, mas se não houver muitos desses sinais e se você não os definir demasiado "complicado" em dobro, poderá não ser nada) . Assim, em C ++, as matrizes de adjacência associativa estendida podem ser definidas da seguinte forma: std :: map <std :: pair <int, int>, std :: vector> ou std :: map <std :: pair <int, int>, std :: vector, com o primeiro valor em "vetor-valor-por-chave" é o peso da aresta e, em seguida, as designações numéricas de seus recursos são localizadas.

Referências:

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: Per. do inglês - M .: Williams Publishing House, 2011.
2. Harari Frank. Teoria dos grafos. M .: Mir, 1973.
O relatório do autor sobre esses mesmos vetores e matriz associativa de adjacência:
3. Chernoukhov S.A. Vetor de adjacência e matriz de adjacência associativa como formas de representação e armazenamento de 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 na implementação dos resultados de desenvolvimentos inovadores e maneiras de resolvê-los" (Saratov, 14 de setembro de 2019). - Sterlitamak: AMI, 2019, p. 65-69
Fontes úteis da Internet sobre o tópico:
4.prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html