¿Qué es un grafo?
Lección 2 de 14 del curso Grafos - Serie de Estructuras de Datos #9 de Coddy.
Un grafo es una estructura de datos que modela un conjunto de cosas y las conexiones entre ellas. Las cosas se llaman vértices (o nodos) y las conexiones se llaman aristas.
Los grafos están en todas partes. Las redes sociales son grafos (las personas son vértices, las amistades son aristas). Los mapas de carreteras son grafos (las intersecciones son vértices, las calles son aristas). El internet, los árboles de dependencias y los mapas de juegos son todos grafos.
En este curso nos enfocamos en un grafo no dirigido: si una arista conecta a u y v, entonces v también está conectado a u. No hay dirección. Usaremos enteros como las claves de los vértices para mantener las cosas simples.
Internamente almacenaremos el grafo como una lista de adyacencia: un mapa de cada vértice a la lista de sus vecinos. Esto hace que buscar los vecinos de un vértice sea un único acceso al mapa, que es lo que la mayoría de los algoritmos de grafos necesitan.
Las operaciones que construiremos en nuestra clase Graph son:
- addVertex: Añadir un nuevo vértice sin aristas todavía.
- addEdge: Conectar dos vértices.
- hasEdge: Comprobar si dos vértices están conectados.
- getNeighbors: Obtener la lista de vecinos de un vértice.
- removeEdge: Desconectar dos vértices.
- size: Contar cuántos vértices tiene el grafo.
¡Vamos a construir una clase Graph!
Pruébalo tú mismo
Esta lección no incluye un desafío de código.