Representación de Grafos: Matriz y Lista de Adyacencia

Un grafo consta de:

• Un conjunto finito de nodos (vértices)
• Un conjunto finito de aristas, relaciones entre nodos. Las aristas pueden contener peso/valor/coste.

Las cuatro formas más comunes de representar un grafo son:

• Matriz de adyacencia
• Lista de adyacencia
• Matriz de incidencia
• Lista de incidencia

La matriz de adyacencia es una matriz 2D de tamaño n x n donde n es el número de nodos de un grafo. Sea la matriz 2D matriz[][], una casilla matriz[i][j] = 1 indica que hay una relación del nodo i al nodo j. La matriz de adyacencia también se utiliza para representar grafos con algún peso, entonces si matriz[i][j] = p, entonces hay una relación del nodo i al nodo j con peso wp.

Esta representación es más fácil de implementar y seguir. Eliminar una arista es O(1) porque solo se reemplaza el valor en la casilla correspondiente. Sin embargo, consume O(n^2) en espacio. Incluso si el gráfico es disperso y contiene pocas relaciones, se consume el mismo espacio. Además, añadir un nuevo nodo es consume O(n^2) y encontrar los nodos adyacentes a un nodo es O(n).

Para la lista de adyacencia se utiliza un arreglo o hash table. El tamaño de este es igual al número de nodos. Sea el arreglo un array[]. Una entrada array[i] representa la lista de nodos adyacentes al nodo i-esimo.

A partir de la próxima clase vamos a implementar algoritmos de búsqueda. ¡Nos vemos allá!