Representación de Grafos

Representación de los Grafos

Un grafo dirigido o un grafo no dirigido puede representarse por medio de:

• Matriz Adyacente
• Lista de Adyacencia
• Arreglos para la Lista de Adyacencia

Matriz Adyacente

El tamaño de la matriz de un grafo será determinada mediante la cantidad de vectores del grafo (V). Entonces, se dirá que la matriz es de (V,V).

La matriz de un grafo se define como:

Ejemplo:

En este grafo los vértices son:

V={1, 2, 3}

y los enlaces son:

E= { (1,2), (1,3), (3,2) }

Como la cantidad de vértices es 3 entonces la matriz será de 3*3… es decir A[3,3]

Pero antes de llenar la matriz hay que tener clara las posiciones en ella.

Tomando en cuenta los enlaces E= { (1,2), (1,3), (3,2) } donde el primer dígito de cada enlace corresponde a la fila y el segundo corresponde a la columna. Es decir:

• Para el primer enlace (1,2) se llenara con un 1 en la fila 1, columna 2
• Para el segundo enlace (1,3) se llenara con un 1  en la fila 1, columna 3
• Para el tercer enlace (3,2) se llenara con 1 en la fila 3, columna 2
• Todas las demás posiciones se llenaran con 0 ya que no existe ningún enlace para ellas.

Lista Adyacente

Para un grafo se realiza una lista de adyacencia para cada vértice que tengan adyacente otro vertice.

Para el siguiente grafo, se hará las siguientes listas:

• Para el vértice 1 tendrá una lista con el 2 y el 3
• Para el vértice 3 tendrá una lista con el 2

Arreglos para lista de adyacencia

Se utilizan arreglos para implementar la lista de adyacencia.

• Para el primer vértice se guardan los valores 2 y 3
• Para separar las listas se guarda un 0
• Como el vértice 2 no tiene enlace con otro vértice se guarda un 0
• Para el vértice 3 se guarda un 2
• Se termina con un 0 para marcar el termino de la lista