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

129

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?

magiix
fonte
21
A estrutura que você usa não depende do idioma, mas do problema que você está tentando resolver.
avakar
1
Eu quis dizer para uso geral como o algoritmo djikstra, fiz esta pergunta porque não sei se vale a pena tentar a implementação da lista vinculada porque é mais difícil de codificar do que a matriz de adjacência.
7609 Magiix
As listas em C ++ são tão fáceis quanto digitar std::list(ou melhor ainda std::vector).
21410 avakar
1
@avakar: ou std::dequeou std::set. Depende da maneira como o gráfico mudará com o tempo e de quais algoritmos você pretende executar neles.
Alexandre C.

Respostas:

125

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)
Mark Byers
fonte
as listas vinculadas são mais difíceis de codificar, você acha que vale a pena dedicar algum tempo à implementação?
7608 magiix
11
@magiix: Sim, eu acho que você deve entender como código vinculado listas, se necessário, mas também é importante para não reinventar a roda: cplusplus.com/reference/stl/list
Mark Byers
alguém pode fornecer um link com um código limpo para, por exemplo, pesquisar a primeira pesquisa no formato de listas vinculadas?
7605 magiix
78

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 2 /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 2 (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 2 /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 2 ) 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.

chaveiro
fonte
9
+1 para obter informações, mas isso deve ser corrigido pela estrutura de dados real usada para armazenar as listas de adjacências. Convém armazenar para cada vértice sua lista de adjacências como um mapa ou um vetor; nesse caso, os números reais em suas fórmulas precisam ser atualizados. Além disso, cálculos semelhantes podem ser usados ​​para avaliar pontos de equilíbrio quanto à complexidade do tempo de algoritmos específicos.
Alexandre C.
3
Sim, esta fórmula é para um cenário específico. Se você quer uma resposta áspera, vá em frente e usar esta fórmula, ou modificá-lo de acordo com suas especificações, conforme necessário (por exemplo, a maioria das pessoas tem um computador de 64 bits hoje :))
Keyser
1
Para os interessados, a fórmula do ponto de ruptura (número máximo de arestas médias em um gráfico de n nós) é e = n / sonde sestá o tamanho do ponteiro.
Deceleratedcaviar
33

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.

insira a descrição da imagem aqui

John Red
fonte
Caso não se saiba se o gráfico é denso ou esparso, seria correto afirmar que a complexidade do espaço para uma lista de adjacências seria O (v + e)?
Para algoritmos mais práticos, uma das operações mais importantes é a iteração através de todas as arestas que saem de um determinado vértice. Você pode adicioná-lo à sua lista - é O (grau) para AL e O (V) para AM.
máximo
@johnred, não é melhor dizer que Adicionar um vértice (tempo) para AL é O (1) porque, em vez de O (en), porque na verdade não adicionamos arestas ao adicionar um vértice. Adicionar uma aresta pode ser tratado como uma operação separada. Para AM, faz sentido prestar contas, mas mesmo lá, precisamos apenas inicializar linhas e colunas relevantes do novo vértice para zero. A adição de arestas, mesmo para AM, pode ser contabilizada separadamente.
precisa saber é
Como adicionar um vértice a AL O (V)? Temos que criar uma nova matriz, copiar os valores anteriores para ela. Deve ser O (v ^ 2).
Alex_ban
19

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.

Alex Ntousias
fonte
e se você usar dicionários para armazenar a lista de adjacências, isso fornecerá a presença de uma borda no tempo amortizado de O (1).
Rohith Yeravothula 27/10/2018
10

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
insira a descrição da imagem aqui

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 2 . 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 2 ). (Você pode apenas usar a parte triangular superior da matriz para determinar todas as arestas, mas será novamente Θ (n 2 ))

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

insira a descrição da imagem aqui
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

Muhammed Kadir
fonte
7

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.

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

Nerd binário
fonte
Obrigado, eu vou verificar esta biblioteca
magiix
+1 para o gráfico de reforço. Este é o caminho a percorrer (exceto é claro se é para fins educacionais)
Tristram Gräbener
5

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.)

Evgeni Sergeev
fonte
2
Para algoritmos como DFS e BFS, se você usar uma matriz, precisará verificar a linha inteira sempre que desejar encontrar nós adjacentes, enquanto você já possui nós adjacentes em uma lista adjacente. Por que você pensa an adjacency list is as good as a matrixnesses casos?
realUser404
@ realUser404 Exatamente, a varredura de uma linha inteira da matriz é uma operação O (n). As listas de adjacência são melhores para gráficos esparsos quando você precisa atravessar todas as arestas de saída; elas podem fazer isso em O (d) (d: grau do nó). Porém, as matrizes têm melhor desempenho de cache do que as listas de adjacência, devido ao acesso seqüencial; portanto, para gráficos um pouco densos, a varredura de uma matriz pode fazer mais sentido.
Jochem Kuijpers
3

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).

deceleratedcaviar
fonte
Não entendo a parte d = (4 * 300) / (300 * 300), não deveria ser d = 4 / (300 * 300)? Desde que a fórmula é d = e / n^2.
Saurabh 06/06
2

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?

ChrisOdney
fonte
1

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).

max
fonte
1

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.

justcoding121
fonte
Para matriz de adjacência, remova o vértice recebe O (V ^ 2) e não O (V)
Saurabh
Sim. Mas se você usar um dicionário para rastrear os índices da matriz, ele diminuirá para O (V). Dê uma olhada nesta implementação RemoveVertex .
justcoding121