Estructura de Datos

La principal desventaja de usar una matriz de adyacencia para representar un grafo dirigido es que requiere un espacio 12(n2) aun si el grafo dirigido tiene menos de n 2 cos. Sólo leer o examinar la matriz puede llevar un tiempo O ( n 2) , lo cual invalidaríalos algoritmos O(n) para la manipulación de grafos dirigidos con O ( n ) arcos.Para evitar esta desventaja, se puede utilizar otra representación común para un grafo dirigido G - (V, A) llamada representación con lista de adyacencia. La lista de adyacencia para un vértice i es una lista, en algún orden, de todos los vértices adyacentes a i. Se puede representar G por medio de un arreglo CABEZA, donde CABEZA[:] es un apuntador a la lista de adyacencia del vértice i. La representación con lista de adyacencia de un grafo dirigido requiere un espacio proporcional a la suma del número de vértices más el número de arcos; se usa bastante cuando el número de arcos es mucho menor que n'. Sin embargo, una desventaja potencial de la representacion con lista de adyaccia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que puede haber O(n) vértices en la lista de adyacencia para el vértice i.

Bibliografia.
Matrices de Adyacencia.15 mayo 2010
http://docencia.udea.edu.co/regionalizacion/teoriaderedes/representacionu1.html