Un lista de adyacencia es una estructura de datos que se utiliza para representar un gráfico donde cada nodo del gráfico almacena una lista de sus vértices vecinos.

Representación gráfica de gráfico dirigido a lista de adyacencia

Características de la Lista de Adyacencia:

• El tamaño de la matriz está determinado por el número de nodos de la red.
• El número de aristas del gráfico se calcula fácilmente.
• La lista de adyacencia es una matriz irregular .

¿Cómo construir una lista de adyacencia?

Es muy fácil y sencillo construir una lista de adyacencia para un gráfico; a continuación se detallan ciertos pasos que debe seguir:

• Crear una matriz de listas vinculadas de tamaño norte , donde N es el número de vértices del gráfico.
• Cree una lista vinculada de vértices adyacentes para cada vértice del gráfico.
• Para cada borde (u,v) en el gráfico, agregue en a la lista enlazada de en , y añadir en a la lista enlazada de en si el gráfico no está dirigido, de lo contrario agregue en a la lista de en si está dirigido desde en a en . (En el caso de gráficos ponderados, almacene el peso junto con las conexiones).

Aplicaciones de la Lista de Adyacencia:

• El algoritmo de Dijkstra , Primera búsqueda en amplitud , y Primera búsqueda en profundidad Utilice listas de adyacencia para representar gráficos.
• Procesamiento de imágenes : Las listas de adyacencia se pueden utilizar para representar las relaciones de adyacencia entre píxeles de una imagen.
• Desarrollo de juegos : Estas listas se pueden usar para almacenar información sobre las conexiones entre diferentes áreas o niveles. Los desarrolladores del juego usan gráficos para representar mapas o niveles del juego.

Ventajas de utilizar una lista de Adyacencia:

• Una lista de adyacencia es simple y fácil de entender.
• Agregar o eliminar aristas de un gráfico es rápido y sencillo.

Desventajas de usar una lista de Adyacencia:

• En las listas de adyacencia, acceder a los bordes puede llevar más tiempo que en la matriz de adyacencia.
• Requiere más memoria que la matriz de adyacencia para gráficos densos.

¿Qué más puedes leer?

• Significado y definición de Matriz de adyacencia en DSA
• Agregar y eliminar bordes en la representación de la lista de adyacencia de un gráfico
• Convertir la matriz de adyacencia en una representación de lista de adyacencia del gráfico
• Convertir la lista de adyacencia en una representación de matriz de adyacencia de un gráfico
• Comparación entre la representación de la lista de adyacencia y la matriz de adyacencia del gráfico