Clase 5 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
Un grafo consta de:
Las cuatro formas más comunes de representar un grafo son:
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á!
