5 Representación

Se puede visualizar un grafo pintando sus vértices como puntos y sus aristas como líneas entre los puntos correspondientes.

¿Cuáles son las operaciones que se quieren realizar con un grafo (y sus componentes)?

Se puede almacenar un grafo con tres métodos básicos:

• una matriz de adyacencia
  • matriz cuatrada, y en el caso simple, binaria (y simétrica si no es digrafo) que codifica si existe una arista entre dos vértices
  • complejidad de memoria $\Omega(n^2)$
• listas de adyacencia
  • lista o array de vértices que contiene en cada entrada una lista de los vértices adyacentes
  • complejidad de memoria $\Theta(n+m)$
• tablas de dispersión
  • lista o array de vértices que contiene en cada entrada una tabla de dispersión de los vértices adyacentes
  • complejidad de memoria $\Theta(n+m)$

¿Cuáles son las principales ventajas y desventajas de cada uno de los métodos?