Lista de adyacencia

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.

• Una implementación sugerida por Guido van Rossum utiliza una tabla hash para asociar cada vértice de un grafo con una matriz de vértices adyacentes. En esta representación, un vértice puede representarse mediante cualquier objeto que pueda ser objeto hash. No existe una representación explícita de las aristas como objetos. ^[1]
• Cormen et al. sugieren una implementación en la que los vértices se representan mediante números de índice. ^[2] Su representación utiliza una matriz indexada por número de vértice, en la que la celda de la matriz 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 puntos finales 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 puntos finales de la arista).
• La estructura de lista de incidencia orientada a objetos sugerida por Goodrich y Tamassia tiene clases especiales de objetos de vértice y objetos de borde. Cada objeto de vértice tiene una variable de instancia que apunta a un objeto de colección que enumera los objetos de borde vecinos. A su vez, cada objeto de borde apunta a los dos objetos de vértice en sus puntos finales. ^[3] Esta versión de la lista de adyacencia utiliza más memoria que la versión en la que se enumeran directamente los vértices adyacentes, pero la existencia de objetos de borde explícitos le permite una flexibilidad adicional para almacenar información adicional sobre los bordes.

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 | ² /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 | ² −| V |)/2 ≈ V ² aristas, lo que permite bucles, podemos hacer que d = | E |/| V | ² denote la densidad del grafo. 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 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.

• Eppstein, David (1996). "Apuntes de la clase ICS 161: Algoritmos gráficos".

• La biblioteca Boost Graph implementa una lista de adyacencia eficiente
• Estructuras de datos abiertas, Sección 12.2, Lista de adyacencia: un gráfico como una colección de listas, Pat Morin