LISTA DE ADYACENCIA

lISTAS DE ADYACENCIA

Estructura de Datos II

Ingeniería en Computación

O1

Lista de adyacencia

Este método es útil de usarlo cuando un grafo tiene muchos vertices y pocas aristas. En esta representación se utiliza una lista enlazada por cada vertice v del grafo que tenga vertices adyacentes desde el.El grafo completo incluye dos partes:* un directorio*un conjunto de listas enlazadas

Definición

DEFINICIÓN

• Hay una entrada en el directorio por cada nodo del grafo
• La entrada al directorio del nodo i apunta a una lista enlazada que representa los nodos que son conectados al nodo i
• Cada registro de la listaenlazada tiene dos campos:
• un identificador de nodo
• un enlace al siguiente elemento de la lista
• La lista enlazada representa arcos

ejemplo

resuelve el siguiente ejemplo

GRACIAS