Representación

LOS GRAFOS SE PUEDEN REPRESENTAR DE 3 MANERAS DIFERENTES

1 Matriz de Adyacencia

2 Lista de Adyacencia

3 Arreglos para la Lista de Adyacencia.

MATRIZ ADYACENTE

La Matriz Adyacente A de un Grafo G=(V,E) tiene V*V elementos y se define como:

VENTAJAS Y DESVENTAJAS 
DE LA MATRIZ DE ADYACENCIA

ventajas:

-Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo.

-Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar en la matriz.

-Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz por ella misma N veces hasta obtener la matriz nula

desventajas:

-Se requiere un almacenamiento |v|*|v|. Es decir O(n2).

-Solo al leer o examinar la matriz puede llevar un tiempo de O(n2).

LISTA ADYACENTE

La lista de adyacencia para un vértice v es una lista enlazada de todos los vértices w adyacentes a v.

Un grafo puede ser representado por |v| listas de adyacencias, una para cada vértice.

VENTAJAS Y DESVENTAJAS 
DE LAS LISTAS DE ADYACENCIA

ventajas:

-La lista de adyacencia requiere un espacio proporcional a la suma del número de vértices más el número de enlaces

– hace buen uso de la memoria

-Se utiliza bastante cuando el número de enlaces es mucho menor que O(n2)

desventajas:

-La representación con lista de adyacencia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que  pueden haber O(n) vértices en la lista de adyacencia. Para el vértice i.

UTILIZACION DE ARREGLOS 
PARA LA LISTA DE ADYACENCIA

Se utilizan los arreglos para implementar  la Lista de Adyacencia:

Ejemplo: