Lista de adyacencia

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 para su uso en programas de computadora.

Detalles de implementacion

El gráfico que se muestra arriba tiene esta representación de lista de adyacencia:
a	adyacente a	antes de Cristo
b	adyacente a	C.A
C	adyacente a	a, b

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 bordes 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 las aristas.

• Una implementación sugerida por Guido van Rossum utiliza una tabla hash para asociar cada vértice de un gráfico con una matriz de vértices adyacentes. En esta representación, un vértice puede estar representado por cualquier objeto hashable. No existe una representación explícita de los bordes como objetos.
• Cornen et al. sugiera una implementación en la que los vértices estén representados por números índice. 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 individualmente de los vértices vecinos de ese vértice. En esta representación, los nodos de la lista enlazada individualmente pueden interpretarse como objetos de borde; sin embargo, no almacenan la información completa sobre cada borde (solo almacenan uno de los dos extremos del borde) y en los gráficos no dirigidos habrá dos nodos de lista enlazados diferentes para cada borde (uno dentro de las listas para cada uno de los dos). extremos del borde).
• La estructura de lista de incidencias 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 extremos. Esta versión de la lista de adyacencia usa más memoria que la versión en la que los vértices adyacentes se enumeran directamente, pero la existencia de objetos de borde explícitos le permite una mayor flexibilidad para almacenar información adicional sobre los bordes.

Operaciones

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

También es posible, pero no tan eficiente, usar listas de adyacencia para probar si existe o no un borde entre dos vértices específicos. En una lista de adyacencia en la que los vecinos de cada vértice no están ordenados, la prueba de la existencia de un borde se puede realizar 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 este vértice. Si los vecinos se representan como una matriz ordenada, se puede usar la búsqueda binaria en su lugar, tomando un tiempo proporcional al logaritmo del grado.

Compensaciones

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 un borde entre los vértices correspondientes a la fila y la 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 bordes), una lista de adyacencia es significativamente más eficiente en cuanto al 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 forma 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 el espacio, haciendo coincidir el uso del espacio lineal de una lista de adyacencia,

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 admitir esta operación.

Estructuras de datos

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 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 alrededor de 2⋅(32/8)| mi | = 8| mi | bytes de espacio, donde | mi | es el número de aristas del gráfico.

Teniendo en cuenta que un gráfico simple no dirigido puede tener como máximo (| V | −| V |)/2 ≈ V aristas, permitiendo bucles, podemos hacer que d = | mi |/| V | denote la densidad del gráfico. Entonces, 8| mi | > | V | /8 cuando | mi |/| 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 gráfico debe ser lo suficientemente escaso para justificar una representación de lista de adyacencia.

Además del compromiso 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, se debe escanear una fila completa, lo que lleva O (| V |) tiempo. Si hay un borde entre dos vértices dados se puede determinar a la vez 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.