¿Qué tiempo O(n) nos lleva representar un grafo dirigido con matrices de adyacencia? ¿ es ventajoso o no? ¿Qué otro método podemos usar?

Figura 1:Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.

Figura 2: Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.

Para representar un grafo dirigido se pueden emplear varias estructuras de datos: la selección apropiada depende de las operaciones que se aplicarán a los vértices y a los arcos del grafo
Una representación común para un grafo dirigido G=(v,a) es la matriz de adyacencia. Supóngase que V {1,2…,n}. la matriz de adyacencia para g es una matriz A de dimensión nxn, de elementos booleanos, donde a [i,j] es verdadero sí, y solo sí existe un arco que vaya del vértice i al j . Con frecuencia se exhibirán matrices de adyacencia con 1 par verdadero y 0 para falso; las matrices de adyacencia pueden incluso obtenerse de esa forma. En la representación con una matriz de adyacencia, el tiempo de acceso requerido a un elemento es independiente del tamaño de V y A.
Así la representación con matrices de adyacencia es útil en los logaritmos para grafos en los cuales suele ser necesario saber si un arco dado está presente.
Algo muy relacionado es la representación con matriz de adyacencia etiquetada de un grafo dirigido, donde A[i,j] es la etiqueta del árbol que va del vértice i al vértice j. si no existe un arco de i a j, debe emplearse como entrada para A[i,j] un valoer que no pueda ser una etiqueta valida.
La principal desventaja de usar una matriz de adyacencia para representar un grafo dirigido es que requiere un Ω(n2) aún si el grafo dirigido tiene menos de n2 arcos. Solo leer o examinar la matriz puede llevar un tiempo O(n2), lo cual invalidara los 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 pude representar G por medio de un arreglo CABEZA, donde CABEZA [i] 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 de números de vértices mas el numero de arcos; se usa bastante cuando el numero de arcos es mucho menor que n2. Sin embargo una desventaja potencial es de la representación con listas de adyacencia es que puede llevar 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.

Teniendo en cuenta estas consideraciones se ha optado por realizar una mezcla de ambas representaciones intentando aprovechar de alguna forma las ventajas que ambas poseen. Por otra parte siguiendo con la idea de tratar tanto los grafos dirigidos como los no dirigidos bajo una misma estructura, la estructura elegida posee dos apariencias ligeramente diferentes para tratar de forma adecuada cada uno de estos dos tipos de grafos.

La estructura consiste (en el caso de que tengamos un grafo dirigido en una lista de vértices donde cada uno de estos posee dos listas, una de aristas incidentes a él y otra de adyacentes. Cada vez que se añade una arista al grafo se inserta en la lista de aristas adyacentes del vértice origen y en la de incidentes del vértice destino. De esta forma la estructura desplegada se asemejaría a una matriz de adyacencia en la cual hay una arista por cada 1 y el índice de la matriz es la posición dentro de la lista de vértices.

Bibliografía

http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/grafos.htm
Estructuras de datos y algoritmos: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman