¿Alguna vez te has preguntado cómo funciona el GPS para encontrar la ruta más corta? ¿O cómo las redes sociales sugieren amigos? La respuesta está en los grafos, una de las estructuras de datos más versátiles en programación.
En esta guía completa aprenderás qué son los grafos, sus tipos, cómo implementarlos en Python y los algoritmos más importantes para trabajar con ellos. Incluye ejemplos de código listos para usar.
Perfecta para estudiantes de programación, desarrolladores que quieren reforzar estructuras de datos, o cualquiera preparándose para entrevistas técnicas.
- ¿Qué es un Grafo en Programación? Definición y Conceptos Básicos
- Elementos de un Grafo
- 6 Tipos de Grafos en Estructuras de Datos (Con Ejemplos)
- Cómo Implementar un Grafo en Python: Código Paso a Paso
- Implementación de Grafos: Matriz de Adyacencia y Lista de Adyacencia
- Matriz de Adyacencia vs Lista de Adyacencia: Comparación Visual
- Complejidad Algorítmica de los Métodos del Grafo
- 3 Algoritmos Esenciales de Grafos: BFS, DFS y Dijkstra
- Casos de Uso Reales de Grafos
- Conclusión
Imagina un mapa de ciudades conectadas por carreteras: las ciudades serían los nodos y las carreteras los bordes. Un grafo es un conjunto de nodos. Y cada nodo está conectado a los bordes.
¿Qué es un Grafo en Programación? Definición y Conceptos Básicos
Los nodos se les llama vertices y a los bordes son llamado aristas.
Si antes viste la estructura de datos de árboles, puede que se tengas una referencia de cómo puede ser un grafo.
Elementos de un Grafo
Son dos los elementos que representa a un grafo:
- Nodos (Vértices): Representan entidades o puntos de datos.
- Bordes (Aristas): Conexiones entre los nodos que representan relaciones o transiciones.
6 Tipos de Grafos en Estructuras de Datos (Con Ejemplos)
Existen varias formas de representar a un grafo:
- Grafos Dirigidos: Los bordes tienen una dirección específica.
- Grafos No Dirigidos: Los bordes no tienen dirección.
- Grafos Ponderados: Los bordes tienen un peso o valor asociado.
- Grafos No Ponderados: Todos los bordes tienen el mismo valor.
- Grafos Cíclicos: Contienen al menos un ciclo (camino que comienza y termina en el mismo nodo).
- Grafos Acíclicos: No contienen ciclos.
Cómo Implementar un Grafo en Python: Código Paso a Paso
Veamos cómo podemos implementar un grafo simple utilizando un diccionario en Python:
Este código implementa un grafo no dirigido usando lista de adyacencia con un diccionario de Python. La clase Graph inicializa un diccionario vacío (self.graph) donde cada clave es un nodo y su valor es una lista de nodos vecinos.
class Graph:
def __init__(self):
self.graph = {}
def add_node(self, node):
if node not in self.graph:
self.graph[node] = []
def add_edge(self, node1, node2):
if node1 not in self.graph:
self.add_node(node1)
if node2 not in self.graph:
self.add_node(node2)
self.graph[node1].append(node2)
self.graph[node2].append(node1) # Para grafos no dirigidos
def display(self):
for node in self.graph:
print(f"{node}: {' '.join(map(str, self.graph[node]))}")
# Ejemplo de uso
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 1)
g.display()
El método add_node() crea nodos aislados, mientras que add_edge() conecta dos nodos bidireccionalmente: primero verifica que ambos nodos existan (creándolos si es necesario), luego agrega cada nodo a la lista de vecinos del otro (self.graph[node1].append(node2) y viceversa).
El método display() recorre el diccionario e imprime cada nodo con sus conexiones en formato legible.
En el ejemplo, se crean tres aristas (1-2, 2-3, 3-1) formando un triángulo donde cada nodo tiene exactamente dos vecinos, y display() muestra esta estructura como: «1: 2 3», «2: 1 3», «3: 2 1».
Implementación de Grafos: Matriz de Adyacencia y Lista de Adyacencia
Existen dos formas principales de implementar un grafo en programación: la matriz de adyacencia y la lista de adyacencia. Ambas tienen sus ventajas y desventajas dependiendo del tipo de grafo y las operaciones que se necesiten realizar. Veamos cada una en detalle:
1. Matriz de Adyacencia
Una matriz de adyacencia es una matriz cuadrada de tamaño V x V. Donde V es el número de vértices en el grafo. El valor en la posición (i, j) de la matriz es 1. Ojo, esto ocurre si hay una arista del vértice i al vértice j. Es 0 en caso contrario.
Ventajas:
- Acceso rápido (O(1)) para verificar si existe una arista entre dos vértices.
- Fácil de implementar y entender.
Desventajas:
- Consume mucho espacio (O(V^2)) incluso para grafos dispersos.
- Agregar o eliminar un vértice es costoso (O(V^2)).
Implementación en Python:
Este código implementa un grafo usando una matriz de adyacencia, que es esencialmente una tabla de V×V (donde V es el número de vértices).
Al inicializar GraphMatrix(4), se crea una matriz de 4×4 llena de ceros, donde cada celda representa si existe o no una conexión entre dos nodos.
class GraphMatrix:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def add_edge(self, u, v):
self.graph[u][v] = 1
self.graph[v][u] = 1 # Para grafos no dirigidos
def remove_edge(self, u, v):
self.graph[u][v] = 0
self.graph[v][u] = 0 # Para grafos no dirigidos
def print_graph(self):
for row in self.graph:
print(row)
# Ejemplo de uso
g = GraphMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.print_graph()
Cuando llamamos a add_edge(0, 1), el código coloca un «1» tanto en la posición [0][1] como en [1][0] de la matriz, indicando que hay una arista bidireccional entre los nodos 0 y 1 (por eso es un grafo no dirigido). El método remove_edge() hace lo opuesto: coloca ceros para «borrar» la conexión.
Finalmente, print_graph() muestra la matriz completa, donde cada fila representa un nodo y cada columna indica con 1 o 0 si ese nodo tiene conexión con los demás.
En el ejemplo, después de agregar las aristas (0-1), (0-2), (1-2) y (2-3), verías una matriz donde puedes visualizar rápidamente todas las conexiones del grafo, aunque este método consume O(V²) de memoria, lo que puede ser ineficiente para grafos grandes con pocas conexiones.
2. Lista de Adyacencia
Una lista de adyacencia es una colección de listas no ordenadas o arrays. El tamaño de la colección es igual al número de vértices. Cada lista describe los vértices adyacentes a un vértice particular.
Ventajas:
- Ahorra espacio en grafos dispersos O(V+E).
- Agregar un vértice es relativamente fácil.
Desventajas:
- El recorrido es más lento cuando verifica si existe la arista. Lo cual sería el peor caso con una complejidad de O(V)
Implementación en Python:
from collections import defaultdict
class GraphList:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u) # Para grafos no dirigidos
def remove_edge(self, u, v):
self.graph[u].remove(v)
self.graph[v].remove(u) # Para grafos no dirigidos
def print_graph(self):
for vertex in self.graph:
print(f"{vertex}: {' '.join(map(str, self.graph[vertex]))}")
# Ejemplo de uso
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.print_graph()
Matriz de Adyacencia vs Lista de Adyacencia: Comparación Visual
Ambas implementaciones tienen sus usos específicos. La matriz de adyacencia es preferible cuando el grafo es denso y se necesitan operaciones rápidas de verificación de aristas.
Y la lista de adyacencia es más eficiente en términos de espacio para grafos dispersos. Además, es preferible cuando se necesita iterar sobre los vecinos de un vértice frecuentemente.
Por ende, debes saber elegir la representación correcta. Esta tabla te ayudará a decidir según tu caso de uso:
| Criterio | Matriz de Adyacencia | Lista de Adyacencia |
|---|---|---|
| Espacio en memoria | O(V²) – Ocupa mucho espacio | O(V + E) – Más eficiente |
| Verificar si existe arista | O(1) – Muy rápido | O(V) – Puede ser lento |
| Iterar sobre vecinos | O(V) – Debe revisar toda la fila | O(grado del nodo) – Muy rápido |
| Agregar/eliminar arista | O(1) – Inmediato | O(1) promedio – Rápido |
| Mejor para… | Grafosdensos(muchas aristas) | Grafosdispersos(pocas aristas) |
| Ejemplo de uso | Red de vuelos completa entre ciudades | Red social (pocos amigos vs millones de usuarios) |
💡 Tip Pro: Si tu grafo tiene más de 50% de las aristas posibles, usa matriz. Si tiene menos del 20%, usa lista de adyacencia. En la mayoría de casos reales, la lista de adyacencia es la mejor opción.
Complejidad Algorítmica de los Métodos del Grafo
Para un grafo con Matriz de Adyacencia, su complejidad algoritmica es en todos los casos: O(n^2)
Y para uno con Lista de Adyacencia, su complejidad es en el caso promedio de O(n+m). Y en el peor caso, con un grafo completo, O(n^2)
3 Algoritmos Esenciales de Grafos: BFS, DFS y Dijkstra
Existen diversos algoritmos para recorrer un grafo. Algunos más optimos que otros. Estos 3 son los más comunes:
- Búsqueda en Amplitud (BFS): Con complejidad temporal O(V + E)
- Búsqueda en Profundidad (DFS): Con complejidad temporal O(V + E)
- Algoritmo de Dijkstra (camino más corto): Con complejidad temporal O((V + E) log V)
Veamos un ejemplo de implementación de BFS:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=" ")
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
# Ejemplo de uso
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("BFS partiendo del nodo 'A':")
bfs(graph, 'A')
Casos de Uso Reales de Grafos
Los grafos no son solo teoría abstracta: están detrás de muchas aplicaciones que usas a diario. Mira estos casos de uso para que te ayuden a reconocer cuándo aplicarlo en tus propios proyectos.
🌐 Redes Sociales (Grafo de Amistades)
Imagina Facebook, Instagram o LinkedIn. Cada usuario es un nodo, y cada relación de amistad o conexión es una arista. Los grafos permiten:
- Sugerir amigos en común (encontrando nodos conectados)
- Detectar comunidades o grupos de interés
- Calcular «grados de separación» entre usuarios
Ejemplo práctico: Cuando LinkedIn te sugiere «Personas que quizás conozcas», está usando algoritmos de grafos para explorar tu red de conexiones.
🎬 Sistemas de Recomendación
Netflix, Spotify y Amazon usan grafos para conectar usuarios con contenido similar:
- Nodos: Usuarios y productos/películas/canciones
- Aristas: Interacciones (vistas, likes, compras)
El algoritmo recorre el grafo para encontrar patrones: «Si te gustó la Serie A y otros usuarios que la vieron también vieron la Serie B, probablemente te guste B».
🗺️ GPS y Navegación
Google Maps y Waze modelan el mundo como un grafo gigante:
- Nodos: Intersecciones o puntos de interés
- Aristas: Calles o carreteras (con peso = distancia o tiempo)
Algoritmos como Dijkstra o A* encuentran la ruta más corta entre dos puntos considerando tráfico en tiempo real.
⚙️ Compiladores (Grafos de Dependencias)
Cuando compilas código, el compilador usa grafos para:
- Resolver dependencias entre módulos (qué archivo debe compilarse primero)
- Detectar dependencias circulares (ciclos en el grafo)
- Optimizar el orden de ejecución de instrucciones
Ejemplo: Si el archivo main.py importa utils.py, y utils.py importa config.py, el compilador construye un grafo dirigido para determinar el orden correcto de carga.
🖥️ Redes de Computadoras
Internet es esencialmente un grafo masivo:
- Nodos: Routers, servidores, dispositivos
- Aristas: Conexiones de red
Protocolos de enrutamiento usan grafos para encontrar el camino más eficiente para enviar paquetes de datos de un punto A a un punto B, incluso si algunos nodos fallan.
Conclusión
Ya conoces los fundamentos de los grafos en Python (aplica para cualquier lenguaje), es hora de elevar tu conocimiento al siguiente nivel:
- Practica: Implementa un sistema de recomendación simple usando grafos
- Profundiza: Lee el tutorial sobre Algoritmo de Dijkstra explicado paso a paso
- Desafío: Intenta resolver problemas de LeetCode sobre grafos (con soluciones comentadas)
Recordemos que no es la única estructura de datos que existe. Tenemos Hashes, Listas, Pilas, Colas y entre otras más que debes aprender y dominar.
💌 ¿Te resultó útil esta guía? Suscríbete al canal de whatsapp para más contenido de valor.
📢 Comparte este post con alguien que esté aprendiendo Python o preparándose para entrevistas técnicas. Le será muy útil.
👉 Únete a mi Canal de WhatsApp para más recursos
👉 Sigueme en mis redes sociales para más contenido de programación y productividad