Representación en memoria enlazada de un grafo

Los grafos se representan en memoria enlazada mediante listas de adyacencia.

Una lista de adyacencia, se define de la siguiente manera: Para un vértice i es una lista en cierto orden formada por todos los vértices adyacentes [a,i]. Se puede representar un grafo por medio de un arreglo donde cabeza de i es un apuntador a la lista de adyacencia al vértice i.

Veamos el siguiente grafo dirigido:

Representacion en memoria enlazada de un grafo

La lista de adyacencia, que se obtuvo a partir del grafo anterior es la siguiente:

Lista de adyacencia de un grafo

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz

Publicado en Estructura de datos

Suscríbete:

who's online