O que é melhor, listas de adjacência ou matrizes de adjacência para problemas de gráfico em C ++?

O que é melhor, listas de adjacência ou matriz de adjacência, para problemas gráficos em C ++? Quais são as vantagens e desvantagens de cada um?

Depende do problema.

Matriz de adjacência

• Usa memória O (n ^ 2)
• É rápido procurar e verificar a presença ou ausência de uma aresta específica
  entre dois nós O (1)
• É lento para percorrer todas as arestas
• É lento adicionar / excluir um nó; uma operação complexa O (n ^ 2)
• É rápido adicionar uma nova aresta O (1)

Lista de adjacências

• O uso da memória depende do número de arestas (não do número de nós), o
  que pode economizar muita memória se a matriz de adjacência for escassa
• Encontrar a presença ou ausência de aresta específica entre dois nós
  é um pouco mais lento do que com a matriz O (k); onde k é o número de nós vizinhos
• É rápido para iterar em todas as arestas, porque você pode acessar qualquer vizinho de nó diretamente
• É rápido adicionar / excluir um nó; mais fácil que a representação matricial
• É rápido adicionar uma nova aresta O (1)

Essa resposta não é apenas para C ++, pois tudo mencionado é sobre as estruturas de dados, independentemente da linguagem. E, minha resposta é assumir que você conhece a estrutura básica de listas e matrizes de adjacência.

Memória

Se a memória é sua principal preocupação, você pode seguir esta fórmula para um gráfico simples que permite loops:

Uma matriz de adjacência ocupa n ² /8 Espaço de bytes (um bit por entrada).

Uma lista de adjacência ocupa espaço 8e, onde e é o número de arestas (computador de 32 bits).

Se definirmos a densidade do gráfico como d = e / n ² (número de arestas dividido pelo número máximo de arestas), podemos encontrar o "ponto de interrupção" em que uma lista ocupa mais memória que uma matriz:

8e> n ² /8 , quando d> 1/64

Portanto, com esses números (ainda específicos de 32 bits), o ponto de interrupção chega a 1/64 . Se a densidade (e / n ² ) for maior que 1/64, será preferível uma matriz se você quiser economizar memória.

Você pode ler sobre isso na wikipedia (artigo sobre matrizes de adjacência) e em muitos outros sites.

Nota : Pode-se melhorar a eficiência de espaço da matriz de adjacência usando uma tabela de hash em que as chaves são pares de vértices (somente não direcionados).

Iteração e pesquisa

As listas de adjacências são uma maneira compacta de representar apenas as arestas existentes. No entanto, isso tem o custo de uma pesquisa possivelmente lenta de arestas específicas. Como cada lista possui o grau de um vértice, o pior caso de verificação de uma borda específica pode se tornar O (n), se a lista não estiver ordenada. No entanto, procurar os vizinhos de um vértice se torna trivial e, para um gráfico esparso ou pequeno, o custo de iterar pelas listas de adjacências pode ser insignificante.

As matrizes de adjacência, por outro lado, usam mais espaço para fornecer tempo de pesquisa constante. Como existe toda entrada possível, é possível verificar a existência de uma borda em tempo constante usando índices. No entanto, a pesquisa de vizinhos usa O (n), pois você precisa verificar todos os possíveis vizinhos. A desvantagem óbvia do espaço é que, para gráficos esparsos, muito preenchimento é adicionado. Veja a discussão sobre memória acima para obter mais informações sobre isso.

Se você ainda não tiver certeza do que usar : A maioria dos problemas do mundo real produz gráficos esparsos e / ou grandes, mais adequados para representações de listas de adjacências. Eles podem parecer mais difíceis de implementar, mas garanto que não. Quando você escreve um BFS ou DFS e deseja buscar todos os vizinhos de um nó, fica a apenas uma linha de código. No entanto, observe que não estou promovendo listas de adjacência em geral.

Ok, eu compilei as complexidades de tempo e espaço das operações básicas em gráficos.
A imagem abaixo deve ser auto-explicativa.
Observe como a Matriz de Adjacência é preferível quando esperamos que o gráfico seja denso e como a Lista de Adjacência é preferível quando esperamos que o gráfico seja esparso.
Eu fiz algumas suposições. Pergunte-me se uma complexidade (tempo ou espaço) precisa de esclarecimentos. (Por exemplo, para um gráfico esparso, considero En uma pequena constante, pois presumi que a adição de um novo vértice adicionará apenas algumas arestas, porque esperamos que o gráfico permaneça esparso mesmo depois de adicionar esse vértice.)

Por favor, diga-me se houver algum erro.

Depende do que você está procurando.

Com matrizes de adjacência, você pode responder rapidamente a perguntas sobre se uma aresta específica entre dois vértices pertence ao gráfico e também pode ter inserções e exclusões rápidas de arestas. A desvantagem é que você precisa usar espaço excessivo, especialmente para gráficos com muitos vértices, o que é muito ineficiente, especialmente se o gráfico for escasso.

Por outro lado, com listas de adjacência , é mais difícil verificar se uma determinada aresta está em um gráfico, porque você precisa pesquisar na lista apropriada para encontrar a aresta, mas elas são mais eficientes em termos de espaço.

Geralmente, porém, as listas de adjacência são a estrutura de dados correta para a maioria dos aplicativos de gráficos.

Vamos supor que temos um gráfico que possui n número de nós e m número de arestas,

Exemplo de gráfico

Matriz de adjacência: estamos criando uma matriz que possui n número de linhas e colunas, para que na memória ocupe espaço proporcional a n ² . Verificar se dois nós nomeados como u e v tem uma borda entre eles levará tempo 1 (1). Por exemplo, verificar (1, 2) é uma aresta que será parecida com a seguinte no código:

if(matrix[1][2] == 1)

Se você deseja identificar todas as arestas, precisará iterar sobre a matriz, pois isso exigirá dois loops aninhados e será necessário Θ (n ² ). (Você pode apenas usar a parte triangular superior da matriz para determinar todas as arestas, mas será novamente Θ (n ² ))

Lista de adjacências: estamos criando uma lista que cada nó também aponta para outra lista. Sua lista terá n elementos e cada elemento apontará para uma lista que possui um número de itens igual ao número de vizinhos desse nó (procure na imagem uma melhor visualização). Portanto, será necessário espaço na memória proporcional a n + m . Verificar se (u, v) é uma aresta levará tempo O (deg (u)) em que deg (u) é igual ao número de vizinhos de u. Porque, no máximo, você precisa iterar sobre a lista apontada pelo u. A identificação de todas as arestas terá Θ (n + m).

Lista de adjacências do exemplo de gráfico

Você deve fazer sua escolha de acordo com suas necessidades. Por causa da minha reputação, não pude colocar imagem de matriz, desculpe por isso

Se você estiver analisando a análise gráfica em C ++, provavelmente o primeiro lugar para começar seria a biblioteca de gráficos boost , que implementa vários algoritmos, incluindo o BFS.

• Documentos da Biblioteca de Gráficos de Boost

EDITAR

Esta pergunta anterior sobre o SO provavelmente ajudará:

how-to-create-ac-boost-não dirigida-graph-and-transversal-it-in-depth-primeiro-searc h

Isso é melhor respondido com exemplos.

Pense no Floyd-Warshall, por exemplo. Temos que usar uma matriz de adjacência, ou o algoritmo será assintoticamente mais lento.

Ou, e se for um gráfico denso em 30.000 vértices? Então, uma matriz de adjacência pode fazer sentido, pois você armazenará 1 bit por par de vértices, em vez dos 16 bits por borda (o mínimo necessário para uma lista de adjacências): isso é 107 MB, e não 1,7 GB.

Mas para algoritmos como DFS, BFS (e aqueles que o utilizam, como Edmonds-Karp), pesquisa com prioridade primeiro (Dijkstra, Prim, A *) etc., uma lista de adjacência é tão boa quanto uma matriz. Bem, uma matriz pode ter uma ligeira aresta quando o gráfico é denso, mas apenas por um fator constante não digno de nota. (Quanto? É uma questão de experimentar.)

Para adicionar à resposta do keyser5053 sobre o uso de memória.

Para qualquer gráfico direcionado, uma matriz de adjacência (a 1 bit por borda) consome n^2 * (1) bits de memória.

Para um gráfico completo , uma lista de adjacência (com ponteiros de 64 bits) consomen * (n * 64) bits de memória, excluindo a sobrecarga da lista.

Para um gráfico incompleto, uma lista de adjacência consome 0bits de memória, excluindo a sobrecarga da lista.

Para uma lista de adjacências, você pode usar a fórmula a seguir para determinar o número máximo de arestas ( e) antes que uma matriz de adjacência seja ideal para memória.

edges = n^2 / spara determinar o número máximo de arestas, onde sestá o tamanho do ponteiro da plataforma.

Se o gráfico estiver atualizando dinamicamente, você poderá manter essa eficiência com uma contagem média de arestas (por nó) de n / s.

Alguns exemplos com ponteiros de 64 bits e gráfico dinâmico (um gráfico dinâmico atualiza a solução de um problema com eficiência após as alterações, em vez de recalculá-lo do zero toda vez que uma alteração é feita.)

Para um gráfico direcionado, onde né 300, o número ideal de arestas por nó usando uma lista de adjacências é:

= 300 / 64
= 4

Se conectarmos isso à fórmula de keyser5053 d = e / n^2(onde eestá a contagem total de arestas), podemos ver que estamos abaixo do ponto de interrupção ( 1 / s):

d = (4 * 300) / (300 * 300)
d < 1/64
aka 0.0133 < 0.0156

No entanto, 64 bits para um ponteiro podem ser um exagero. Se você usar números inteiros de 16 bits como deslocamento de ponteiro, podemos ajustar até 18 arestas antes do ponto de interrupção.

= 300 / 16
= 18

d = ((18 * 300) / (300^2))
d < 1/16
aka 0.06 < 0.0625

Cada um desses exemplos ignora a sobrecarga das listas de adjacência ( 64*2para um vetor e ponteiros de 64 bits).

Dependendo da implementação da Matriz de Adjacência, o 'n' do gráfico deve ser conhecido anteriormente para uma implementação eficiente. Se o gráfico é muito dinâmico e requer expansão da matriz de vez em quando, isso também pode ser considerado uma desvantagem?

Se você usar uma tabela de hash em vez da matriz ou lista de adjacências, obterá melhor ou o mesmo tempo de execução grande e espaço para todas as operações (verificar uma borda O(1), obter todas as bordas adjacentes O(degree)etc.).

Embora exista um fator de sobrecarga constante, tanto para o tempo de execução quanto para o espaço (a tabela de hash não é tão rápida quanto a lista vinculada ou a pesquisa de matriz e ocupa um espaço extra decente para reduzir colisões).

Vou apenas abordar a questão da representação regular da lista de adjacências, já que outras respostas cobriram outros aspectos.

É possível representar um gráfico na lista de adjacências com a consulta EdgeExists em tempo constante amortizado, aproveitando as estruturas de dados Dictionary e HashSet . A idéia é manter os vértices em um dicionário e, para cada vértice, mantemos um conjunto de hash fazendo referência a outros vértices com os quais ela possui arestas.

Uma pequena desvantagem nessa implementação é que ela terá complexidade de espaço O (V + 2E) em vez de O (V + E) como na lista de adjacências regular, uma vez que as arestas são representadas duas vezes aqui (porque cada vértice tem seu próprio conjunto de hash de arestas). Porém, operações como AddVertex , AddEdge , RemoveEdge podem ser feitas no tempo amortizado O (1) com esta implementação, exceto para RemoveVertex que O (V) como matriz de adjacência. Isso significa que, além da simplicidade da implementação, a matriz de adjacência não tem nenhuma vantagem específica. Podemos economizar espaço no gráfico esparso com quase o mesmo desempenho nesta implementação da lista de adjacências.

Dê uma olhada nas implementações abaixo no repositório Github C # para obter detalhes. Observe que, no gráfico ponderado, ele usa um dicionário aninhado em vez da combinação de conjunto de hash de dicionário para acomodar o valor do peso. Da mesma forma, no gráfico direcionado, existem conjuntos de hash separados para arestas de entrada e saída.

Algoritmos avançados

Nota: Acredito que usando a exclusão lenta, podemos otimizar ainda mais a operação RemoveVertex para O (1) amortizado, mesmo que eu não tenha testado essa idéia. Por exemplo, ao excluir, marque o vértice como excluído no dicionário e limpe lentamente as bordas órfãs durante outras operações.