Lista de Adjacências e Representação Matricial do Gráfico
Sarah Chen
⚡ Resumo Inteligente
A lista de adjacência e a representação matricial de um grafo armazenam vértices e arestas na memória, permitindo que algoritmos percorram as redes. A lista de adjacência utiliza listas encadeadas por vértice, enquanto a matriz de adjacência utiliza uma grade quadrada bidimensional.
Embora pareçam diferentes, todos tipos de gráficos podem ser representados de maneira semelhante. Geralmente, existem dois tipos de representação gráfica:
- Matriz de adjacência
- Lista de Adjacência
Lista de Adjacência
Uma lista de adjacência consiste em listas encadeadas. Cada vértice é considerado um índice de um array, e cada elemento representa uma lista encadeada. Essas listas encadeadas contêm os vértices que compartilham uma aresta com o vértice do índice.
Aqui está um exemplo de uma lista de adjacência:
Seja um grafo com V vértices e E arestas. A complexidade espacial da lista de adjacência é O(V + E), que escala com o número de arestas reais em vez de cada par possível de vértices.
A complexidade espacial no pior caso torna-se O(V²) Se o grafo dado for um grafo completo, é porque cada vértice se conecta a todos os outros vértices.
Matriz de adjacência
Uma matriz de adjacência é composta por um array bidimensional. Para um grafo com V vértices, o tamanho da matriz será V × V.
Dizer matrix[i][j] = 5Significa que existe uma aresta entre o nó i e o nó j com peso 5.
Vejamos o seguinte grafo e sua matriz de adjacência:
Nós construímos o Matriz 2D usando estas etapas:
Passo 1) O vértice A possui uma aresta direta com B, e o peso dessa aresta é 5. Portanto, a célula na linha A e coluna B será preenchida com o valor 5. As demais células na linha A serão preenchidas com zero.
Passo 2) O vértice B possui uma aresta direta com C, e o peso dessa aresta é 4. Portanto, a célula na linha B e coluna C será preenchida com o valor 4. As células restantes na linha B serão preenchidas com zero, visto que B não possui nenhuma aresta de saída para nenhum outro nó.
Passo 3) O vértice C não possui arestas diretas com nenhum outro vértice. Portanto, a linha C será preenchida com zeros.
Passo 4) O vértice D possui uma aresta direcionada com A e C.
- A célula na linha D e coluna A terá o valor 7. A célula na linha D e coluna C terá o valor 2.
- O restante das células da linha D será preenchida com zeros.
Passo 5) O vértice E possui uma aresta direcionada com B e D. A célula na linha E e coluna B terá o valor 6. A célula na linha E e coluna D terá o valor 3. As demais células na linha E serão preenchidas com zeros.
Aqui estão alguns pontos a serem observados:
- O grafo não possui auto-laços quando a diagonal principal da matriz de adjacência é 0.
- O gráfico é direcionado se as células em (a, b) e (b, a) não tiverem o mesmo valor. Caso contrário, o gráfico é não direcionado.
- O gráfico é considerado ponderado se o valor de qualquer célula for maior que 1.
O principal problema da matriz de adjacência é que ela requer espaço quadrado. Mesmo arestas que não existem ainda alocam células na memória.
Por exemplo, se tivermos um grafo com 100 nós, serão necessárias 10,000 células para armazená-lo em RAMCom menos arestas no grafo, alocar tanta memória pode ser um desperdício. Portanto, a complexidade espacial usando a matriz de adjacência é O(N²), onde N é o número de nós no grafo.
Lista de adjacência vs. Matriz de adjacência
Antes de escolher uma representação, é útil comparar ambos os modelos lado a lado nas operações que predominam nas cargas de trabalho reais de grafos:
| Divisão de | Matriz de adjacência | Lista de Adjacência |
|---|---|---|
| Complexidade do espaço | O(V²) | O(V + E) |
| Adicionar um vértice | O(V²) | O (1) |
| Adicione uma borda | O (1) | O (1) |
| Remover uma aresta | O (1) | O(E) |
| Verifique se a aresta (i, j) existe. | O (1) | O(grau de i) |
| Iterar sobre os vizinhos de i | O (V) | O(grau de i) |
| Melhor para | Grafos densos, consultas frequentes às arestas | Grafos esparsos, tarefas com muitas travessias |
Resumindo, a matriz de adjacência é superior em termos de tempo constante para buscas de arestas, enquanto a lista de adjacência é superior em termos de memória e iteração de vizinhos, razão pela qual algoritmos como BFS, DFS e Dijkstra geralmente são usados em conjunto com listas de adjacência.
Vantagens e desvantagens da representação gráfica
Cada representação apresenta suas próprias vantagens e desvantagens. Conhecer os pontos fortes e fracos de ambos os modelos ajuda você a escolher o mais adequado para o problema que está resolvendo.
Vantagens da Matriz de Adjacência:
- Consultas de existência de arestas em tempo constante O(1) entre qualquer par de vértices.
- A indexação fixa facilita a implementação de algoritmos baseados em matrizes, como o de Floyd-Warshall e o de fecho transitivo.
- As arestas ponderadas se encaixam naturalmente em uma única célula da matriz.
Desvantagens da Matriz de Adjacência:
- Desperdiça memória O(V²) quando o grafo é esparso.
- Adicionar um novo vértice requer redimensionar toda a matriz.
- Iterar sobre os vizinhos de um único vértice leva O(V), mesmo quando o vértice tem apenas algumas arestas.
Vantagens da lista de adjacência:
- Utiliza apenas memória O(V + E), o que é próximo da contagem real de arestas em grafos esparsos.
- Adicionar um novo vértice ou aresta é O(1).
- Algoritmos de busca em largura (BFS) e busca em profundidade (DFS) iteram pelos vizinhos em O(grau), resultando em um tempo de execução geral de O(V + E).
Desvantagens da lista de adjacência:
- Verificar se uma aresta específica existe leva tempo O(grau) em vez de O(1).
- A localidade do cache é mais fraca porque as listas encadeadas estão espalhadas pela memória.
- As arestas ponderadas precisam de um campo complementar ou de uma lista de pares, o que complica um pouco a estrutura de dados.
Quando usar lista de adjacência versus matriz de adjacência
A escolha da representação depende da densidade do grafo e das operações que você executa com mais frequência. Use este guia rápido para escolher a estrutura adequada:
- Prefira a matriz de adjacência Quando o grafo é denso (E está próximo de V²), quando as arestas raramente mudam e quando seu algoritmo pergunta "existe uma aresta entre i e j?" muitas vezes.
- Prefira a lista de adjacências quando o grafo é esparso (E é muito menor que V²), quando o conjunto de vértices ou arestas cresce durante a execução e quando você percorre o grafo com BFS, DFS ou Algoritmo de caminho mais curto de Dijkstra.
- Prefiro um modelo misto (lista de adjacência mais um conjunto hash de arestas) quando você precisa de iteração rápida de vizinhos e consultas de arestas O(1), ao custo de memória extra.
Bibliotecas gráficas modernas, como NetworkX e igraph, usam listas de adjacência por padrão porque a maioria dos grafos do mundo real — redes sociais, mapas rodoviários, páginas da web, dependências de pacotes — são esparsos e exigem muitas travessias.
