•          Para la representación de grafos se deben considerar:

- Representación del conjunto de nodos o vértices, V.

- Representación del conjunto de aristas, A.

–         Ojo: las aristas son relaciones “muchos a muchos” entre nodos...

Representación del conjunto de aristas A para un grafo dirigido.

–         Mediante matriz de adyacencia.

–         Mediante listas de adyacencia.

Matriz de adyacencia para un grafo no dirigido.

• Sea M de tipo GrafoNoEtiq, G= (V, A).
• M[v, w] = cierto ⇔ (v, w) ∈ A

Grafo no dirigido → Matriz simétrica: M[i, j] = M[j, i].

Resultado: se desperdicia la mitad de la memoria.

Ventajas y desventajas al utilizar Matrices de adyacencia.

Uso de memoria

•          k₂ bytes/etiqueta

•          Memoria usada: k₂n²

Ventajas

•          Representación y operaciones muy sencillas.

•          Eficiente para el acceso a una arista dada.

Inconvenientes

•          El número de nodos del grafo no puede cambiar.

•          Si hay muchos nodos y pocas aristas (a<<n²) se desperdicia mucha memoria.

Listas de adyacencia para un grafo no dirigido.

tipo Nodo= entero (1..n)

       tipo GrafoNoEtiq= array [1..n] de Lista[Nodo]

•          Sea R de tipo GrafoNoEtiq, G= (V, A).

•          La lista R[v] contiene los w tal que (v, w) ∈ A.

Grafo no dirigido à Las aristas están repetidas.

Resultado: también se desperdicia memoria.

 

Ventajas y desventajas al utilizar Listas de adyacencia.

Uso de memoria

•          k₁ bytes/puntero, k₂ bytes/etiqueta o nodo

•          Memoria usada: k₁(n+a) + 2k₂a

•          Con matrices de adyacencia: k₂n²

•          ¿Cuál usa menos memoria?

Ventajas

•          Más adecuada cuando a<<n².

Inconvenientes

•          Representación más compleja.

•          Es ineficiente para encontrar las aristas que llegan a un nodo.

Ver el siguiente Link:

https://elibro.bibliotecabuap.elogim.com/es/ereader/bibliotecasbuap/50117?page=460