Representación de grafos

6.1 Matriz de adyacencia: principio de funcionamiento, ventajas y desventajas.

Matriz de adyacencia es una forma de representar un grafo en forma de matriz cuadrada de tamaño n x n, donde n es el número de vértices en el grafo. Los elementos de la matriz indican la presencia o ausencia de aristas entre los vértices:

• Si existe una arista entre los vértices i y j, entonces el elemento A[i][j] = 1 (o el peso de la arista, si el grafo es ponderado).
• Si no hay arista, entonces A[i][j] = 0.

Ejemplo:

Para un grafo con vértices A, B, C y aristas (A, B), (B, C) y (C, A) la matriz de adyacencia sería:

Si todos los vértices estuvieran conectados con todos, la matriz de adyacencia se vería así:

Ventajas:

• Simplicidad: fácil de entender e implementar.
• Acceso rápido: verificar la presencia de una arista entre dos vértices se hace en O(1).
• Adecuado para grafos densos: eficiente para grafos con un gran número de aristas.

Desventajas:

• Altos costes de memoria: requiere O(n^2) de memoria, incluso si el grafo tiene pocas aristas (grafo disperso).
• Ineficiencia para grafos dispersos: con un gran número de vértices y pocas aristas, la mayoría de los elementos de la matriz serán ceros, lo que lleva a un uso ineficiente de la memoria.

6.2 Listas de adyacencia: principio de funcionamiento, ventajas y desventajas.

Listas de adyacencia es una forma de representar un grafo en forma de un array de listas. Cada elemento del array corresponde a un vértice del grafo y contiene una lista de todos los vértices adyacentes.

Ejemplo:

Para un grafo con vértices A, B, C y aristas (A, B), (B, C) y (C, A) las listas de adyacencia serían:

Si todos los vértices estuvieran conectados con todos, las listas de adyacencia se verían así:

Ventajas:

• Uso eficiente de memoria: requiere O(V + E) de memoria, donde V es el número de vértices, E es el número de aristas, lo que lo hace más adecuado para grafos dispersos.
• Facilidad de recorrido: conveniente para realizar operaciones de recorrido de grafos (por ejemplo, búsqueda en anchura o profundidad).

Desventajas:

• Acceso más complejo: verificar la presencia de una arista entre dos vértices requiere O(k) tiempo, donde k es el número de vecinos del vértice.
• Estructura menos obvia: más compleja en implementación y comprensión en comparación con la matriz de adyacencia.

6.3 Comparación de diferentes métodos de representación de grafos.

Vamos a comparar los diferentes métodos de representación de grafos.

1. Matriz de adyacencia:

• Simplicidad: fácil de entender e implementar.
• Memoria: requiere O(n^2) de memoria, lo que puede ser ineficiente para grafos dispersos.
• Rapidez de acceso: verificar la presencia de una arista se realiza en O(1).
• Adecuado: para grafos densos con un gran número de aristas.

2. Listas de adyacencia:

• Simplicidad: menos obvias que la matriz de adyacencia, pero también comprensibles.
• Memoria: requieren O(V + E) de memoria, lo que es más eficiente para grafos dispersos.
• Rapidez de acceso: verificar la presencia de una arista se realiza en O(k), donde k es el número de vecinos del vértice.
• Adecuadas: para grafos dispersos con pocas aristas.

Comparación:

La matriz de adyacencia es más adecuada para grafos densos, donde la mayoría de los vértices están conectados por aristas, ya que proporciona un acceso rápido a la información sobre las aristas y es simple de implementar.

Las listas de adyacencia son preferibles para grafos dispersos, donde el número de aristas es significativamente menor que el número de pares de vértices posibles. Proporcionan un uso eficiente de la memoria y son convenientes para realizar operaciones de recorrido del grafo.