Lista de adjacência

Em teoria dos grafos, uma lista de adjacência, estrutura de adjacência^[1] ou dicionário^[2] é a representação de todas arestas ou arcos de um grafo em uma lista.

Se o grafo é não direcionado, cada entrada é um conjunto (ou multiconjunto) de dois nós contendo as duas extremidades da aresta correspondente; se ele for dirigido, cada entrada é uma tupla de dois nós, um indicando o nó de origem e o outro denotando o nó destino do arco correspondente.

Normalmente, as listas de adjacência são desordenadas.

Em ciência da computação, uma lista de adjacência é uma estrutura de dados para representar grafos. Em uma representação de lista de adjacência, podemos manter, para cada vértice do grafo, uma lista de todos os outros vértices com os quais ele tem uma aresta (a "lista de adjacência", deste vértice). Por exemplo, a representação sugerida por van Rossum,^[3] em que uma tabela de dispersão (tabela hash) é usada para associar cada vértice com um array de vértices adjacentes, pode ser vista como um exemplo deste tipo de representação. Outro exemplo é a representação encontrada em Cormen et al. em que um array indexado pelos números dos vértices aponta para uma lista simplesmente encadeada dos vizinhos de cada vértice.^[4]

Uma dificuldade com a estrutura da lista de adjacência é que ela não tem lugar óbvio para armazenar dados associados com as arestas de um grafo, tais como o comprimento ou custos das arestas. Para remediar isso, alguns textos, como o de Goodrich e Tamassia,^[5][6] defendem uma variante mais orientada a objeto da estrutura da lista de adjacência, às vezes chamada de lista de incidência, que armazena para cada vértice uma lista de objetos que representam as arestas incidentes a esse vértice. Para completar a estrutura, cada aresta deve apontar de volta para os dois vértices que compõem a sua extremidade. Os objetos extras nesta versão da lista de adjacência aumentam o uso de memória em relação à versão em que vértices adjacentes são listados diretamente, mas estas arestas extras também são um local conveniente para armazenar informações adicionais sobre cada aresta (por exemplo, o seu comprimento).

Ainda uma outra forma de representação é a lista de adjacência com arrays em que um array indexado pelos números dos vértices aponta para arrays contendo os vértices.^[7]

A principal alternativa para a lista de adjacência é a matriz de adjacência. Para um grafo com uma matriz de adjacência esparsa uma representação de lista de adjacências do grafo ocupa menos espaço, porque ele não usa nenhum espaço para representar as arestas que não estão presentes.^[8] Usando uma implementação de listas de adjacência com um simples array em um computador de 32 bits, uma lista de adjacência de um grafo não direcionado requer cerca de 8e bytes de armazenamento, onde e é o número de arestas: cada aresta dá origem a entradas nas duas listas de adjacência e usa quatro bytes cada uma.

Por outro lado, pelo fato de que cada entrada em uma matriz de adjacências requer apenas um bit, elas podem ser representados de uma forma muito compacta, ocupando apenas n²/8 bytes de espaço contíguo, onde n é o número de vértices. Além de apenas evitar desperdício de espaço, essa compactação incentiva a localidade de referência.

Observando que um grafo pode ter no máximo n² arestas (permitindo laços) podemos fazer d = e/n² denotar a densidade do grafo. Então, se 8e > n²/8, a representação de lista de adjacência ocupa mais espaço, o que é verdadeiro quando d > 1/64. Assim, um grafo deve ser muito escasso para uma representação de lista de adjacência ser mais eficiente em termos de memória do que uma matriz de adjacência. No entanto, esta análise só é válida quando a representação é usada para armazenar a estrutura de conectividade do grafo, sem qualquer informação numérica sobre suas arestas.

Além do conflito de escolha relativo ao espaço, as estruturas de dados diferentes também facilitam operações diferentes. É fácil encontrar todos os vértices adjacentes a um vértice dada em uma representação lista de adjacência; você simplesmente le a sua lista de adjacência. Com uma matriz de adjacência em vez disso se tem que pesquisar mais de uma linha inteira, gastando tempo O(n). Se, pelo contrário, deseja realizar um teste de vizinhança em dois vértices (isto é, determinar se eles têm uma aresta entre eles), uma matriz de adjacência proporciona isso na hora. No entanto, este teste de vizinhança em uma lista de adjacências requer tempo proporcional ao número de arestas associado com os dois vértices.

Referências