En teoría de grafos y ciencias de la computación , una lista de adyacencia es una colección de listas desordenadas que se utilizan para representar un grafo finito. Cada lista desordenada dentro de una lista de adyacencia describe el conjunto de vecinos de un vértice particular en el grafo. Esta es una de las varias representaciones de grafos que se usan comúnmente en programas de computadora.
Una representación de lista de adyacencia para un grafo asocia cada vértice del grafo con la colección de sus vértices o aristas vecinos. Existen muchas variaciones de esta idea básica, que difieren en los detalles de cómo implementan la asociación entre vértices y colecciones, en cómo implementan las colecciones, 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.
La operación principal que realiza la estructura de datos de lista de adyacencia es informar una lista de los vecinos de un vértice determinado. Mediante cualquiera de las implementaciones detalladas anteriormente, esto se puede realizar en tiempo constante por vecino. En otras palabras, el tiempo total para informar todos los vecinos de un vértice v es proporcional al grado de v .
También es posible, aunque no tan eficiente, utilizar listas de adyacencia para comprobar si existe o no una arista entre dos vértices especificados. En una lista de adyacencia en la que los vecinos de cada vértice no están ordenados, la comprobación de la existencia de una arista se puede realizar en un tiempo proporcional al grado mínimo de los dos vértices dados, utilizando una búsqueda secuencial a través de los vecinos de este vértice. Si los vecinos se representan como una matriz ordenada, se puede utilizar en su lugar una búsqueda binaria , que tarda un tiempo 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 hay una arista entre los vértices correspondientes a la fila y columna de la celda. Para un grafo disperso (uno 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 términos de espacio que una matriz de adyacencia (almacenada como una matriz bidimensional): el uso de espacio de la lista de adyacencia es proporcional al número de aristas y vértices en el 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 manera más eficiente en términos de espacio, igualando el uso de espacio lineal de una lista de adyacencia, utilizando una tabla hash indexada por pares de vértices en lugar de una matriz.
La otra diferencia significativa entre las listas de adyacencia y las matrices de adyacencia está en la eficiencia de las operaciones que realizan. En una lista de adyacencia, los vecinos de cada vértice pueden enumerarse de manera eficiente, en un tiempo proporcional al grado del vértice. En una matriz de adyacencia, esta operación lleva 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 entre sí en tiempo constante; la lista de adyacencia es más lenta para soportar esta operación.
Para su uso como estructura de datos, la principal alternativa a la lista de adyacencia es la matriz de adyacencia. Debido a que cada entrada en la matriz de adyacencia requiere solo un bit, se puede representar de una manera muy compacta, ocupando solo | V | 2 /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, porque no desperdician espacio para representar aristas que no están presentes. Si se utiliza 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 la cantidad de aristas del grafo.
Observando que un grafo simple no dirigido puede tener como máximo (| V | 2 −| V |)/2 ≈ V 2 aristas, lo que permite bucles, podemos hacer que d = | E |/| V | 2 denote la densidad del grafo. Entonces, 8| E | > | V | 2 /8 cuando | E |/| V | 2 > 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 para justificar una representación de lista de adyacencia.
Además de la compensación de espacio, las diferentes 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 simple como leer la lista. Con una matriz de adyacencia, en cambio, se debe escanear una fila entera, lo que lleva O (| V |) tiempo. 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.
