REPRESENTACIÓN ENLAZADA DE UN GRAFO

Sea G un grafo  dirigido con m nodos. la representación secuencial de G en memoria- o sea, la representación de G por su matriz de adyacencia A- tiene unas cuantas desventajas importantes. en primer lugar, puede ser difícil insertar y eliminar nodos de G. esto es porque el tamaño de A debería de ser cambiado y los nodos deberían ser reordenados, así que habría muchos cambios en la matriz A. mas aun, si el numero de aristas es 0(m) o 0(m log₂ m), entonces la matriz A estará desperdiciada (contendrá muchos ceros); por tanto, se desperdiciara una gran cantidad de espacio. Por tanto, G normalmente se representa en memoria por una representación enlazada, también llamada estructure de adyacencia.

SIG

ADY

NODO

LISTA DE NODOS. cada elemento de la lista NODO corresponderá a un nodo de G y será un 

registro de la forma: