Si alguna vez has usado Google Maps para buscar una ruta o has jugado un videojuego donde la IA te persigue, has interactuado con grafos. Pero, ¿cómo recorre una máquina estos caminos?
Aquí entran los dos reyes de la algoritmia conocidos: DFS (Búsqueda en Profundidad) y BFS (Búsqueda en Amplitud).
Si te estás preparando para las entrevistas técnicas para este 2026, o simplemente quieres mejorar tu lógica de programación, este post no será teoría aburrida: es tu manual de implementación en Python con DFS y BFS.
Antes de iniciar, te invito a que hagas una lectura previa acerca de qué son los árboles en programación y qué es el análisis asintótico. Serán necesarios para comprender el tema a continuación.
Tabla de contenidos
¿Qué es DFS (Búsqueda en Profundidad)?
El DFS es un algoritmo que apuesta por la profundidad. Imagina que entras en un laberinto: DFS elige un camino y lo sigue hasta chocar con una pared (o llegar al final) antes de retroceder. Su lema es: «Todo hacia adelante, retrocede solo si es necesario».
Ficha Técnica del DFS
- Estructura de Datos: Pila (Stack). LIFO (Last In, First Out).
- Estrategia: Profundidad agresiva.
- Complejidad Temporal: O(V + E) (Vértices + Aristas).
- Complejidad Espacial: O(h) (Altura del árbol). Eficiente en memoria.
Implementación de DFS en Python
¿Cómo funciona DFS?
El algoritmo DFS sigue estos pasos:
- Comienza en el nodo raíz (o cualquier nodo inicial)
- Marca el nodo actual como visitado
- Explora recursivamente cada vecino no visitado
- Retrocede cuando no hay más vecinos por explorar
Veamos cómo implementar DFS de tres formas diferentes: recursiva, iterativa y para árboles binarios.
DFS Recursivo (La forma más intuitiva)
class Grafo:
def __init__(self):
self.grafo = {}
def agregar_arista(self, u, v):
if u not in self.grafo:
self.grafo[u] = []
self.grafo[u].append(v)
def dfs_recursivo(self, nodo, visitados=None):
"""
DFS recursivo: explora profundamente antes de retroceder
"""
if visitados is None:
visitados = set()
# Marcar el nodo actual como visitado
visitados.add(nodo)
print(nodo, end=' ')
# Explorar todos los vecinos no visitados
if nodo in self.grafo:
for vecino in self.grafo[nodo]:
if vecino not in visitados:
self.dfs_recursivo(vecino, visitados)
return visitados
# Ejemplo de uso
g = Grafo()
g.agregar_arista(0, 1)
g.agregar_arista(0, 2)
g.agregar_arista(1, 3)
g.agregar_arista(1, 4)
g.agregar_arista(2, 5)
g.agregar_arista(2, 6)
print("Recorrido DFS recursivo desde el nodo 0:")
g.dfs_recursivo(0)
# Salida: 0 1 3 4 2 5 6
DFS Iterativo (Usando una pila explícita)
def dfs_iterativo(self, inicio):
"""
DFS iterativo: usa una pila para simular la recursión
"""
visitados = set()
pila = [inicio]
while pila:
# Sacar el último elemento de la pila
nodo = pila.pop()
if nodo not in visitados:
print(nodo, end=' ')
visitados.add(nodo)
# Agregar vecinos a la pila (en orden inverso para mantener el orden)
if nodo in self.grafo:
for vecino in reversed(self.grafo[nodo]):
if vecino not in visitados:
pila.append(vecino)
return visitados
# Agregar el método a la clase Grafo
Grafo.dfs_iterativo = dfs_iterativo
print("\\nRecorrido DFS iterativo desde el nodo 0:")
g.dfs_iterativo(0)
# Salida: 0 1 3 4 2 5 6
DFS en Árboles Binarios
Para árboles binarios, DFS corresponde a los tres tipos de recorrido que ya conoces:
class NodoArbol:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
self.derecha = None
class ArbolBinario:
def __init__(self):
self.raiz = None
# DFS Preorden (Raíz-Izquierda-Derecha)
def dfs_preorden(self, nodo):
if nodo:
print(nodo.valor, end=' ')
self.dfs_preorden(nodo.izquierda)
self.dfs_preorden(nodo.derecha)
# DFS Inorden (Izquierda-Raíz-Derecha)
def dfs_inorden(self, nodo):
if nodo:
self.dfs_inorden(nodo.izquierda)
print(nodo.valor, end=' ')
self.dfs_inorden(nodo.derecha)
# DFS Postorden (Izquierda-Derecha-Raíz)
def dfs_postorden(self, nodo):
if nodo:
self.dfs_postorden(nodo.izquierda)
self.dfs_postorden(nodo.derecha)
print(nodo.valor, end=' ')
# Crear un árbol de ejemplo
# 1
# / \\
# 2 3
# / \\
# 4 5
arbol = ArbolBinario()
arbol.raiz = NodoArbol(1)
arbol.raiz.izquierda = NodoArbol(2)
arbol.raiz.derecha = NodoArbol(3)
arbol.raiz.izquierda.izquierda = NodoArbol(4)
arbol.raiz.izquierda.derecha = NodoArbol(5)
print("DFS Preorden:")
arbol.dfs_preorden(arbol.raiz) # 1 2 4 5 3
print("\\nDFS Inorden:")
arbol.dfs_inorden(arbol.raiz) # 4 2 5 1 3
print("\\nDFS Postorden:")
arbol.dfs_postorden(arbol.raiz) # 4 5 2 3 1
¿Qué es BFS (Búsqueda en Amplitud)?
El BFS funciona como una señal de Wi-Fi o una gota de agua en un lago: se expande en todas direcciones nivel por nivel. Primero visita a todos los vecinos directos, luego a los vecinos de los vecinos.
Ficha Técnica del BFS
- Estructura de Datos: Cola (Queue). FIFO (First In, First Out).
- Estrategia: Exploración por capas o niveles.
- Complejidad Temporal: O(V + E).
- Complejidad Espacial: O(w) (Ancho máximo del árbol). Consume más memoria.
- Superpoder: Garantiza encontrar el camino más corto en grafos no ponderados.
¿Cómo funciona BFS?
El algoritmo BFS sigue estos pasos:
- Comienza en el nodo raíz y agrégalo a una cola
- Marca el nodo como visitado
- Mientras la cola no esté vacía:
- Saca el primer nodo de la cola
- Explora todos sus vecinos no visitados
- Marca cada vecino como visitado y agrégalo a la cola
Implementación de BFS en Python
BFS para Grafos
from collections import deque
class Grafo:
def __init__(self):
self.grafo = {}
def agregar_arista(self, u, v):
if u not in self.grafo:
self.grafo[u] = []
self.grafo[u].append(v)
def bfs(self, inicio):
"""
BFS: explora nivel por nivel usando una cola
"""
visitados = set()
cola = deque([inicio])
visitados.add(inicio)
resultado = []
while cola:
# Sacar el primer elemento de la cola
nodo = cola.popleft()
resultado.append(nodo)
print(nodo, end=' ')
# Agregar todos los vecinos no visitados a la cola
if nodo in self.grafo:
for vecino in self.grafo[nodo]:
if vecino not in visitados:
visitados.add(vecino)
cola.append(vecino)
return resultado
# Ejemplo de uso
g = Grafo()
g.agregar_arista(0, 1)
g.agregar_arista(0, 2)
g.agregar_arista(1, 3)
g.agregar_arista(1, 4)
g.agregar_arista(2, 5)
g.agregar_arista(2, 6)
print("Recorrido BFS desde el nodo 0:")
g.bfs(0)
# Salida: 0 1 2 3 4 5 6
BFS para Árboles Binarios (Recorrido por Niveles)
from collections import deque
class NodoArbol:
def __init__(self, valor):
self.valor = valor
self.izquierda = None
self.derecha = None
class ArbolBinario:
def __init__(self):
self.raiz = None
def bfs(self):
"""
BFS en árbol binario: recorrido por niveles
"""
if not self.raiz:
return []
resultado = []
cola = deque([self.raiz])
while cola:
nodo = cola.popleft()
resultado.append(nodo.valor)
# Agregar hijos a la cola
if nodo.izquierda:
cola.append(nodo.izquierda)
if nodo.derecha:
cola.append(nodo.derecha)
return resultado
def bfs_por_niveles(self):
"""
BFS que retorna los nodos agrupados por nivel
"""
if not self.raiz:
return []
resultado = []
cola = deque([self.raiz])
while cola:
nivel_actual = []
tamaño_nivel = len(cola)
# Procesar todos los nodos del nivel actual
for _ in range(tamaño_nivel):
nodo = cola.popleft()
nivel_actual.append(nodo.valor)
if nodo.izquierda:
cola.append(nodo.izquierda)
if nodo.derecha:
cola.append(nodo.derecha)
resultado.append(nivel_actual)
return resultado
# Crear árbol de ejemplo
# 1
# / \\
# 2 3
# / \\ \\
# 4 5 6
arbol = ArbolBinario()
arbol.raiz = NodoArbol(1)
arbol.raiz.izquierda = NodoArbol(2)
arbol.raiz.derecha = NodoArbol(3)
arbol.raiz.izquierda.izquierda = NodoArbol(4)
arbol.raiz.izquierda.derecha = NodoArbol(5)
arbol.raiz.derecha.derecha = NodoArbol(6)
print("BFS normal:")
print(arbol.bfs()) # [1, 2, 3, 4, 5, 6]
print("\\nBFS por niveles:")
print(arbol.bfs_por_niveles()) # [[1], [2, 3], [4, 5, 6]]
DFS vs BFS: ¿Cuál usar y cuándo?
Ahora que conoces ambos algoritmos, surge la pregunta: ¿cuándo usar DFS y cuándo BFS? La respuesta depende del problema que estés resolviendo.
Comparación visual y técnica
| Criterio | 🔦 DFS (Profundiad) | 📡 BFS (Amplitud) |
|---|---|---|
| Estructura de datos | Pila (Stack) | Cola (Queue) |
| Complejidad temporal | O(V + E) | O(V + E) |
| Complejidad espacial | O(h) – altura del árbol | O(w) – ancho del árbol |
| Camino más corto | ❌ No garantizado | ✅ Sí (en grafos no ponderados) |
| Uso de memoria | Menos memoria en árboles anchos | Menos memoria en árboles profundos |
| Implementación | Recursiva o iterativa | Iterativa con cola |
| Caso de Uso | Laberintos, Backtracking, Puzzles | GPS, Redes Sociales, Peer-to-Peer |
¿Cuándo usar DFS?
Usa DFS cuando:
- Necesitas explorar todas las posibilidades: Como en problemas de backtracking (sudoku, N-reinas)
- Buscas un camino específico: No necesariamente el más corto
- Trabajas con árboles profundos y estrechos: DFS usa menos memoria
- Detectas ciclos en grafos: DFS es excelente para esto
- Realizas ordenamiento topológico: En grafos dirigidos acíclicos
- Encuentras componentes conectados: En grafos no dirigidos
¿Cuándo usar BFS?
Usa BFS cuando:
- Necesitas el camino más corto: En grafos no ponderados
- Buscas el nodo más cercano: Como vecinos en una red social
- Trabajas con árboles anchos y poco profundos: BFS es más eficiente en memoria
- Exploras por niveles: Como en análisis de redes o propagación
- Necesitas encontrar todos los nodos a una distancia específica
Casos de Uso Real: ¿Dónde se aplica DFS y BFS?
1. Resolver Laberintos (Territorio DFS)
Si solo necesitas encontrar una salida (cualquiera), DFS es tu amigo. Es rápido y agresivo.
def resolver_laberinto_dfs(laberinto, inicio, fin):
"""
Resuelve un laberinto usando DFS
laberinto: matriz donde 0 = camino, 1 = pared
inicio: tupla (fila, columna) del punto inicial
fin: tupla (fila, columna) del punto final
"""
filas = len(laberinto)
columnas = len(laberinto[0])
visitados = set()
camino = []
def es_valido(fila, col):
return (0 <= fila < filas and
0 <= col < columnas and
laberinto[fila][col] == 0 and
(fila, col) not in visitados)
def dfs(fila, col):
# Caso base: llegamos al final
if (fila, col) == fin:
camino.append((fila, col))
return True
# Marcar como visitado
visitados.add((fila, col))
camino.append((fila, col))
# Explorar las 4 direcciones: arriba, derecha, abajo, izquierda
direcciones = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for df, dc in direcciones:
nueva_fila, nueva_col = fila + df, col + dc
if es_valido(nueva_fila, nueva_col):
if dfs(nueva_fila, nueva_col):
return True
# Backtrack: este camino no lleva a la salida
camino.pop()
return False
if dfs(inicio[0], inicio[1]):
return camino
return None
# Ejemplo de laberinto (0 = camino, 1 = pared)
laberinto = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
inicio = (0, 0)
fin = (4, 4)
camino = resolver_laberinto_dfs(laberinto, inicio, fin)
if camino:
print("Camino encontrado con DFS:")
for paso in camino:
print(paso, end=' -> ')
print("¡SALIDA!")
else:
print("No hay solución")
2. El GPS – El camino más corto (BFS)
Si necesitas encontrar el camino más corto en el laberinto, BFS es la mejor opción.
from collections import deque
def camino_mas_corto_bfs(laberinto, inicio, fin):
"""
Encuentra el camino más corto en un laberinto usando BFS
"""
filas = len(laberinto)
columnas = len(laberinto[0])
# Cola que almacena: (posición actual, camino hasta aquí)
cola = deque([(inicio, [inicio])])
visitados = {inicio}
def es_valido(fila, col):
return (0 <= fila < filas and
0 <= col < columnas and
laberinto[fila][col] == 0 and
(fila, col) not in visitados)
while cola:
(fila, col), camino = cola.popleft()
# ¿Llegamos al final?
if (fila, col) == fin:
return camino
# Explorar vecinos
direcciones = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for df, dc in direcciones:
nueva_fila, nueva_col = fila + df, col + dc
if es_valido(nueva_fila, nueva_col):
visitados.add((nueva_fila, nueva_col))
nuevo_camino = camino + [(nueva_fila, nueva_col)]
cola.append(((nueva_fila, nueva_col), nuevo_camino))
return None
# Usando el mismo laberinto
camino_corto = camino_mas_corto_bfs(laberinto, inicio, fin)
if camino_corto:
print(f"\\nCamino más corto encontrado con BFS ({len(camino_corto)} pasos):")
for paso in camino_corto:
print(paso, end=' -> ')
print("¡SALIDA!")
else:
print("No hay solución")
3. Red Social – Grados de Separación (BFS)
Si quieres saber quién es tu conexión de LinkedIn de 2º grado, necesitas BFS.
from collections import deque
class RedSocial:
def __init__(self):
self.usuarios = {}
def agregar_usuario(self, usuario):
if usuario not in self.usuarios:
self.usuarios[usuario] = []
def agregar_amistad(self, usuario1, usuario2):
self.agregar_usuario(usuario1)
self.agregar_usuario(usuario2)
self.usuarios[usuario1].append(usuario2)
self.usuarios[usuario2].append(usuario1)
def grados_separacion(self, persona1, persona2):
"""
Encuentra el número de conexiones entre dos personas
"""
if persona1 not in self.usuarios or persona2 not in self.usuarios:
return -1
if persona1 == persona2:
return 0
cola = deque([(persona1, 0)]) # (persona, distancia)
visitados = {persona1}
while cola:
persona_actual, distancia = cola.popleft()
# Explorar amigos
for amigo in self.usuarios[persona_actual]:
if amigo == persona2:
return distancia + 1
if amigo not in visitados:
visitados.add(amigo)
cola.append((amigo, distancia + 1))
return -1 # No hay conexión
def encontrar_camino(self, persona1, persona2):
"""
Encuentra la cadena de conexiones entre dos personas
"""
if persona1 not in self.usuarios or persona2 not in self.usuarios:
return None
if persona1 == persona2:
return [persona1]
cola = deque([(persona1, [persona1])])
visitados = {persona1}
while cola:
persona_actual, camino = cola.popleft()
for amigo in self.usuarios[persona_actual]:
if amigo == persona2:
return camino + [amigo]
if amigo not in visitados:
visitados.add(amigo)
cola.append((amigo, camino + [amigo]))
return None
# Ejemplo de uso
red = RedSocial()
# Agregar amistades
amistades = [
("Ana", "Bob"),
("Bob", "Carlos"),
("Carlos", "Diana"),
("Diana", "Eva"),
("Ana", "Felipe"),
("Felipe", "Eva")
]
for persona1, persona2 in amistades:
red.agregar_amistad(persona1, persona2)
# Encontrar grados de separación
grados = red.grados_separacion("Ana", "Eva")
print(f"Grados de separación entre Ana y Eva: {grados}")
# Encontrar el camino
camino = red.encontrar_camino("Ana", "Eva")
if camino:
print(f"Camino de conexión: {' -> '.join(camino)}")
4: Sistema de Archivos (DFS)
Los sistemas operativos usan DFS para recorrer directorios y subdirectorios.
class Archivo:
def __init__(self, nombre, es_directorio=False):
self.nombre = nombre
self.es_directorio = es_directorio
self.hijos = [] if es_directorio else None
def agregar_hijo(self, hijo):
if self.es_directorio:
self.hijos.append(hijo)
def __repr__(self):
return f"{'📁' if self.es_directorio else '📄'} {self.nombre}"
class SistemaArchivos:
def __init__(self):
self.raiz = Archivo("/", es_directorio=True)
def listar_todos_dfs(self, nodo=None, nivel=0):
"""
Lista todos los archivos y directorios usando DFS
"""
if nodo is None:
nodo = self.raiz
# Imprimir el archivo/directorio actual con indentación
print(" " * nivel + str(nodo))
# Explorar recursivamente los subdirectorios
if nodo.es_directorio:
for hijo in nodo.hijos:
self.listar_todos_dfs(hijo, nivel + 1)
def buscar_archivo_dfs(self, nombre, nodo=None):
"""
Busca un archivo específico usando DFS
"""
if nodo is None:
nodo = self.raiz
if nodo.nombre == nombre:
return nodo
if nodo.es_directorio:
for hijo in nodo.hijos:
resultado = self.buscar_archivo_dfs(nombre, hijo)
if resultado:
return resultado
return None
def contar_archivos(self, nodo=None):
"""
Cuenta el total de archivos (no directorios) usando DFS
"""
if nodo is None:
nodo = self.raiz
if not nodo.es_directorio:
return 1
total = 0
for hijo in nodo.hijos:
total += self.contar_archivos(hijo)
return total
# Crear estructura de directorios
fs = SistemaArchivos()
# Directorio home
home = Archivo("home", es_directorio=True)
fs.raiz.agregar_hijo(home)
# Usuario
usuario = Archivo("usuario", es_directorio=True)
home.agregar_hijo(usuario)
# Documentos
documentos = Archivo("documentos", es_directorio=True)
usuario.agregar_hijo(documentos)
documentos.agregar_hijo(Archivo("reporte.pdf"))
documentos.agregar_hijo(Archivo("notas.txt"))
# Imágenes
imagenes = Archivo("imagenes", es_directorio=True)
usuario.agregar_hijo(imagenes)
imagenes.agregar_hijo(Archivo("foto1.jpg"))
imagenes.agregar_hijo(Archivo("foto2.png"))
print("Estructura completa del sistema de archivos (DFS):")
fs.listar_todos_dfs()
print(f"\\nTotal de archivos: {fs.contar_archivos()}")
# Buscar un archivo específico
archivo_buscado = fs.buscar_archivo_dfs("reporte.pdf")
if archivo_buscado:
print(f"\\nArchivo encontrado: {archivo_buscado}")
Ejercicios para Entrevistas (Challenge)
Si quieres conseguir ese puesto Senior, intenta resolver estos retos de DFS y BFS sin mirar la solución:
- Detección de Ciclos: ¿Hay un bucle infinito en mis dependencias de paquetes? (Pista: DFS con recursión).
- Número de Islas: Dada una matriz de 1s (tierra) y 0s (agua), cuenta las islas. (Pista: Usa DFS para «hundir» la isla visitada).
- Validar Árbol Simétrico: ¿Es el árbol un espejo de sí mismo? (Pista: BFS por niveles).
Consejos para Dominar DFS y BFS
- Practica visualizando: Dibuja el árbol o grafo en papel y simula el algoritmo paso a paso
- Entiende cuándo usar cada uno: DFS para exploración completa, BFS para caminos más cortos
- Practica problemas en plataformas como LeetCode: Muchos problemas de entrevistas se resuelven con estos algoritmos
- Domina ambas implementaciones: Recursiva e iterativa para DFS
- Piensa en la complejidad espacial: Es crítica en problemas con límites de memoria
Conclusión
Dominar DFS y BFS es lo que separa a un «coder promedio» de un Programador Senior. La clave está en reconocer qué problema estás resolviendo y elegir el algoritmo apropiado. Con la práctica, esto se volverá intuitivo.
- Usa DFS si el espacio de memoria es crítico o necesitas explorar a fondo (backtracking).
- Usa BFS si la respuesta está cerca de la raíz o necesitas la ruta más corta.
Tu siguiente paso:
- Implementa el «Buscador de Islas» en Python y súbelo a tu GitHub.
- Te recomiendo explorar grafos en programación, donde DFS y BFS son herramientas esenciales.
- Investigar sobre algoritmos más avanzados como Dijkstra (para grafos ponderados) o el algoritmo de búsqueda A* (para búsqueda informada).
¿Te ha sido útil esta guía? Te invito a que lo compartas con otros. Puede que les sea de utilidad o les ayude a superar sus límites 🚀.
👉 Únete a mi Canal de WhatsApp para más recursos
👉 Sigueme en mis redes sociales para más contenido de programación y productividad