Representación de Grafos

 

Un grafo Dirigido o No-Dirigido se puede representar mediante:

1. Matriz de Adyacencia
2. Lista de Adyacencia
3. Arreglos para la Lista de Adyacencia.

Sea el siguiente Grafo Dirigido:

 

 

Matriz Adyacente.

 

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

 

 

Ventajas & 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( no hay ciclos) o bien una sucesión periódica de matrices (hay ciclo).

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 & 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 (arcos).  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.

 

Utilización de Arreglos para Listas de Adyacencia.

 

Se utilizan los arreglos para implementar la Lista de Adyacencia: