Representación de Grafos: Matriz y Lista de Adyacencia

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

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á!

Representación de Grafos: Matriz y Lista de Adyacencia

Representación de Grafos: Matriz y Lista de Adyacencia

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces