lista de adyacencia

En teoría de grafos e informática , una lista de adyacencia es una colección de listas no ordenadas que se utiliza para representar un grafo finito . Cada lista no ordenada dentro de una lista de adyacencia describe el conjunto de vecinos de un vértice particular en el grafo. Esta es una de las representaciones de grafos más utilizadas en programas informáticos.

Una representación de lista de adyacencia para un grafo asocia cada vértice del grafo con el conjunto de sus vértices o aristas vecinas. Existen muchas variaciones de esta idea básica, que difieren en los detalles de cómo implementan la asociación entre vértices y conjuntos, en cómo implementan los conjuntos, en si incluyen tanto vértices como aristas o solo vértices como objetos de primera clase, y en qué tipos de objetos se utilizan para representar los vértices y las aristas.

• Una implementación propuesta por Guido van Rossum utiliza una tabla hash para asociar cada vértice de un grafo con un array de vértices adyacentes. En esta representación, un vértice puede representarse mediante cualquier objeto que pueda ser hasheado. No existe una representación explícita de las aristas como objetos. ^{[ 1 ]}
• Cormen et al. proponen una implementación en la que los vértices se representan mediante números de índice. ^{[ 2 ]} Su representación utiliza un arreglo indexado por el número de vértice, en el que la celda del arreglo para cada vértice apunta a una lista enlazada simple de los vértices vecinos de ese vértice. En esta representación, los nodos de la lista enlazada simple pueden interpretarse como objetos de arista; sin embargo, no almacenan la información completa sobre cada arista (solo almacenan uno de los dos extremos de la arista) y en grafos no dirigidos habrá dos nodos de lista enlazada diferentes para cada arista (uno dentro de las listas para cada uno de los dos extremos de la arista).
• La estructura de lista de incidencia orientada a objetos propuesta por Goodrich y Tamassia tiene clases especiales de objetos de vértice y objetos de arista. Cada objeto de vértice tiene una variable de instancia que apunta a un objeto de colección que enumera los objetos de arista vecinos. A su vez, cada objeto de arista apunta a los dos objetos de vértice en sus extremos. ^{[ 3 ]} Esta versión de la lista de adyacencia utiliza más memoria que la versión en la que los vértices adyacentes se listan directamente, pero la existencia de objetos de arista explícitos le otorga mayor flexibilidad para almacenar información adicional sobre las aristas.

La operación principal que realiza la estructura de datos de lista de adyacencia es generar una lista de los vecinos de un vértice dado. Utilizando cualquiera de las implementaciones detalladas anteriormente, esto se puede realizar en tiempo constante por vecino. En otras palabras, el tiempo total para generar la lista de todos los vecinos de un vértice v es proporcional al grado de v .

También es posible, aunque menos eficiente, utilizar listas de adyacencia para comprobar si existe o no una arista entre dos vértices específicos. En una lista de adyacencia donde los vecinos de cada vértice no están ordenados, la comprobación de la existencia de una arista puede realizarse en un tiempo proporcional al grado mínimo de los dos vértices dados, mediante una búsqueda secuencial a través de los vecinos de dicho vértice. Si los vecinos se representan como un arreglo ordenado, se puede utilizar una búsqueda binaria , cuyo tiempo es proporcional al logaritmo del grado.

La principal alternativa a la lista de adyacencia es la matriz de adyacencia , una matriz cuyas filas y columnas están indexadas por vértices y cuyas celdas contienen un valor booleano que indica si existe una arista entre los vértices correspondientes a la fila y columna de la celda. Para un grafo disperso (en el que la mayoría de los pares de vértices no están conectados por aristas), una lista de adyacencia es significativamente más eficiente en cuanto a espacio que una matriz de adyacencia (almacenada como un arreglo bidimensional): el uso de espacio de la lista de adyacencia es proporcional al número de aristas y vértices del grafo, mientras que para una matriz de adyacencia almacenada de esta manera, el espacio es proporcional al cuadrado del número de vértices. Sin embargo, es posible almacenar matrices de adyacencia de forma más eficiente en cuanto a espacio, igualando el uso lineal de espacio de una lista de adyacencia, utilizando una tabla hash indexada por pares de vértices en lugar de un arreglo.

Otra diferencia significativa entre las listas de adyacencia y las matrices de adyacencia radica en la eficiencia de las operaciones que realizan. En una lista de adyacencia, los vecinos de cada vértice se pueden listar de forma eficiente, en un tiempo proporcional al grado del vértice. En una matriz de adyacencia, esta operación requiere un tiempo proporcional al número de vértices del grafo, que puede ser significativamente mayor que el grado. Por otro lado, la matriz de adyacencia permite comprobar si dos vértices son adyacentes en tiempo constante; la lista de adyacencia es más lenta para realizar esta operación.

Para su uso como estructura de datos, la principal alternativa a la lista de adyacencia es la matriz de adyacencia. Dado que cada entrada en la matriz de adyacencia requiere solo un bit, se puede representar de forma muy compacta, ocupando solo | V | ^² /8 bytes de espacio contiguo, donde | V | es el número de vértices del grafo. Además de evitar el desperdicio de espacio, esta compacidad fomenta la localidad de referencia .

Sin embargo, para un grafo disperso, las listas de adyacencia requieren menos espacio, ya que no desperdician espacio para representar aristas que no están presentes. Usando una implementación de matriz simple en una computadora de 32 bits, una lista de adyacencia para un grafo no dirigido requiere aproximadamente 2⋅(32/8) | E | = 8 | E | bytes de espacio, donde | E | es el número de aristas del grafo.

Observando que un grafo simple no dirigido puede tener como máximo ( | V | ² − | V | )/2 ≈ V ² aristas, permitiendo bucles, podemos denotar la densidad del grafo como d = | E | / | V | ^2. Entonces, 8 | E | > | V | ² /8 cuando | E | / | V | ² > 1/64 , es decir, la representación de lista de adyacencia ocupa más espacio que la representación de matriz de adyacencia cuando d > 1/64 . Por lo tanto, un grafo debe ser lo suficientemente disperso como para justificar una representación de lista de adyacencia.

Además de la compensación en espacio, las distintas estructuras de datos también facilitan diferentes operaciones. Encontrar todos los vértices adyacentes a un vértice dado en una lista de adyacencia es tan sencillo como leer la lista. Con una matriz de adyacencia, en cambio, hay que recorrer una fila completa, lo que requiere un tiempo de O ( | V | ) . Con una matriz de adyacencia se puede determinar de inmediato si existe una arista entre dos vértices dados, mientras que con la lista de adyacencia se requiere un tiempo proporcional al grado mínimo de los dos vértices.

• Eppstein, David (1996). "Apuntes de clase de ICS 161: Algoritmos de grafos" . Archivado del original el 4 de enero de 2025.

• La biblioteca Boost Graph implementa una lista de adyacencia eficiente.
• Estructuras de datos abiertas, Sección 12.2, Lista de adyacencia: Un grafo como una colección de listas , Pat Morin