En teoría de grafos e informática , una lista de adyacencia es una colección de listas desordenadas que se utilizan para representar un gráfico finito . Cada lista desordenada dentro de una lista de adyacencia describe el conjunto de vecinos de un vértice particular en el gráfico. Esta es una de varias representaciones de gráficos comúnmente utilizadas en programas de computadora.
Una representación de lista de adyacencia para un gráfico asocia cada vértice del gráfico con la colección de sus vértices o aristas vecinos. Hay 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é Se utilizan tipos de objetos para representar los vértices y aristas.
La operación principal realizada por la estructura de datos de la lista de adyacencia es informar una lista de los vecinos de un vértice determinado. Usando 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 eficaz, 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, se puede realizar la prueba de la existencia de una arista 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 la búsqueda binaria , tomando 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 presente entre los vértices correspondientes a la fila y columna de la celda. Para un gráfico 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 del espacio de la lista de adyacencia es proporcional al número de aristas y vértices en el gráfico, 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 términos de espacio, igualando el uso del 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 se pueden enumerar 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 gráfico, que puede ser significativamente mayor que el grado. Por otro lado, la matriz de adyacencia permite probar 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 usar 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 gráfico. Además de evitar el desperdicio de espacio, esta compacidad favorece la localidad de referencia .
Sin embargo, para un gráfico disperso, las listas de adyacencia requieren menos espacio, porque no desperdician espacio para representar bordes que no están presentes. Usando una implementación de matriz ingenua en una computadora de 32 bits, una lista de adyacencia para un gráfico no dirigido requiere aproximadamente 2⋅(32/8)| mi | = 8| mi | bytes de espacio, donde | mi | es el número de aristas del gráfico.
Observando que un gráfico simple no dirigido puede tener como máximo (| V | 2 −| V |)/2 ≈ V 2 aristas, permitiendo bucles, podemos dejar d = | mi |/| V | 2 denota la densidad del gráfico. Entonces, 8| mi | > | V | 2/8 cuando | _ mi |/| V | 2 > 1/64 , es decir, la representación de la lista de adyacencia ocupa más espacio que la representación de la matriz de adyacencia cuando d > 1/64 . Por tanto, un gráfico debe ser lo suficientemente disperso como para justificar una representación de lista de adyacencia.
Además de la compensación espacial, las diferentes estructuras de datos también facilitan diferentes operaciones. Encontrar todos los vértices adyacentes a un vértice determinado en una lista de adyacencia es tan simple como leer la lista. Con una matriz de adyacencia, se debe escanear una fila completa, lo que lleva O (| V |) tiempo. Si hay un borde entre dos vértices dados se puede determinar de inmediato con una matriz de adyacencia, mientras que requiere un tiempo proporcional al grado mínimo de los dos vértices con la lista de adyacencia.
