Matrices de Adyacencia para representación de Grafos Dirigidos

Iniciaremos diciendo que un grafo dirigido consiste en un conjunto de vértices V y un conjunto de arcos, los vértices también pueden llamarse nodos o puntos, los arcos pueden llamarse arcos dirigidos o líneas dirigidas.

Los arcos son pares ordenados de vértices (A, B), donde A es la cola y B la cabeza del arco, y se expresa como A -> B.

La punta de la flecha esta en el vértice llamado cabeza y la cola en el vértices llamado cola se dice que el arco A -> B va de A a B y B es adyacente a A.

Para la representación de un grafo dirigido se pueden usar varias estructuras de datos, la selección dependerá de las operaciones que se les aplicara a los vértices. Una representación común de un grafo dirigido es la matriz de adyacencia.
Sea G= (V, A) un grafo, donde V= {1, 2, 3. . ., n}. La matriz de adyacencia para G es una matriz booleana de dimensión nxn, donde cada elemento [i, j] vale 1 si y solo si, existe un arco (i, j).
La principal desventaja de usar una matriz de adyacencia para representar un grafo dirigido es que requiere un espacio Ω (n2) aun si el grafo dirigido tiene menos de n2, Solo leer y examinar un matriz de adyacencia puede llevar un tiempo O (n2).

Para evitar esta desventaja se puede utilizar otro método común para un grafo dirigido, llanada representación con lista de adyacencia. El grafo está representado por un arreglo de listas de adyacencia. Sea G= (V, A) un grafo, donde V= {1, 2, 3. . ., n}. 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 H, donde H[i] es un apuntador a la lista de adyacencia del vértice i.

Conclusión
Usar matrices de adyacencia será fácil pero tiene una complejidad de tiempo más cara que usar las listas de adyacencia.

http://es.wikibooks.org/wiki/Estructuras_de_datos_dinamicas/Grafos
http://www.ucfunciones.webs.com/TeoriaDeGrafos/Representacion_de_grafos.pdf