E184 - ADS - Parte 4: DFS y BFS para búsqueda en grafos

Resumen

Cuarto episodio de la serie de algoritmos y estructuras de datos al estilo LeetCode para entrevistas técnicas. Repasa qué es un grafo (nodos y aristas, dirigido o no dirigido, ciclos y DAGs) y cómo modelar un problema como grafo, con el tablero de ajedrez y los movimientos del caballo como ejemplo. Explica BFS (búsqueda por amplitud), que avanza por niveles con una cola, y lo aplica al problema 102 de LeetCode, Binary Tree Level Order Traversal. Después explica DFS (búsqueda por profundidad) y lo aplica a Number of Islands, que equivale a contar componentes conexas. Conclusiones: BFS sirve para explorar por niveles y para el camino más corto en grafos sin pesos, y DFS recorre cada rama hasta el fondo con recursión. En ambos hay que marcar los nodos visitados y definir bien los casos borde para no caer en bucles infinitos. Los participantes comentan que estos algoritmos se resuelven con for, while e if, pero de forma inteligente y sin repetir búsquedas. Entre medio hay una pausa de memes y varias digresiones.

Capítulos

• 00:00
  Introducción a BFS y DFSPresenta el episodio 184: BFS y DFS son dos algoritmos muy usados en entrevistas técnicas de código y se aplican a grafos. Es el cuarto video de la serie de problemas estilo LeetCode.
• 00:34
  Conceptos básicos de grafosUn grafo es un conjunto de nodos (vértices) y aristas (edges), y puede ser dirigido o no dirigido. En un grafo dirigido, del nodo A solo se puede llegar a B si la arista apunta en esa dirección.
• 01:11
  Grafos dirigidos y ciclosMuestra la diferencia entre dirigido y no dirigido, y los ciclos: un camino de un nodo a sí mismo, o A→B y B→A. Estos ciclos generan un grafo cíclico.
• 02:45
  DAGs y recursión seguraLos pipelines y flujos de scripts suelen ser DAGs (grafo acíclico dirigido), porque un ciclo haría que el código no terminara. Hablan de pipelines manuales con llamadas recursivas por error y de la necesidad de una condición de término alcanzable.
• 04:47
  Tablero como grafoUn tablero de ajedrez se modela como grafo con cada casilla como nodo y la adyacencia como arista. Para modelar un problema hay que definir cuáles son los elementos (nodos) y cuál es la relación entre ellos (aristas).
• 06:48
  Movimientos del caballoEl mismo tablero se modela ahora con los movimientos posibles de un caballo, como grafo dirigido con los mismos nodos pero otras conexiones. Los participantes comentan de pasada su afición al ajedrez y a juegos tácticos como XCOM.
• 11:21
  Alcanzabilidad en dos pasosPara saber a dónde llega el caballo en dos movimientos cambian las conexiones, aunque la estructura base sea la misma. Incluye el caso de volver al nodo de origen. Plantea la pregunta de entrevista de cuántos movimientos necesita un caballo para cubrir un tablero de 8x8.
• 12:51
  BFS con el caballoPropone una solución iterativa con una lista de nodos no visitados, una lista de nodos actuales, un `while` hasta vaciar la lista y un contador de iteraciones. Aclara que no es fuerza bruta, porque no repite búsquedas.
• 16:40
  Qué es BFSEsa lógica es Breadth First Search: partir de un nodo inicial y expandirse un nivel a la vez. Con un caballo en el centro hay hasta 8 destinos por movimiento, y en dos movimientos son menos de 64 por las repeticiones. Menciona LeetCode como página para practicar y ver respuestas de otras personas.
• 22:33
  BFS en árbolesUn árbol es un grafo dirigido. Describe raíz, ramas, hojas y profundidad en un árbol binario, y dice que los algoritmos de grafos aplican a árboles.
• 25:00
  Colas para BFSBFS se implementa con una cola (primero en llegar, primero en salir), con la analogía de la fila de un trámite. Se procesa el elemento que llegó primero y se agregan los nuevos al final.
• 26:50
  Ejemplo BFS paso a pasoSobre un grafo con nodo raíz, calcula la profundidad máxima. Usa una cola de vecinos y una lista de revisados para no agregar nodos repetidos. Cris corrige un error de conteo de vecinos en el dibujo.
• 33:32
  Usos de BFSBFS sirve para el camino más corto en grafos sin pesos, para exploración por niveles, para problemas de distancia y para flood fill. Al buscar un destino se puede parar sin recorrer todo el grafo. Cris dice que le parece "fuerza bruta con un if", y Rodo responde que no repite búsquedas. Insiste en estudiar estos algoritmos para entrevistas.
• 39:10
  Problema LeetCode 102Presenta Binary Tree Level Order Traversal: recorrer un árbol binario por niveles, de izquierda a derecha. La salida es un arreglo de arreglos, uno por nivel, y no la profundidad.
• 42:11
  Por qué hay que recorrerDiscuten por qué un computador debe recorrer el grafo aunque a simple vista se vea la profundidad. Rodo responde que los ejemplos simples sirven para validar el algoritmo, pero que con millones de nodos desordenados no es evidente. Sin más información hay que recorrer todo, porque la parte no recorrida podría ser la más profunda.
• 47:18
  BFS por nivelesResponde a la idea de Cris de usar una búsqueda tipo binaria o recursiva: BFS avanza un nivel más en todos los caminos por igual. Puede programarse recursivamente, pero no es necesario, y se puede hacer con una cola y una lista de revisados.
• 48:43
  Heurísticas y casos bordeExplica qué es una heurística: suposiciones para acelerar que pueden fallar. Muestra el input `3 9 20 null null 15 7` y la salida por niveles. Un árbol de un solo elemento debe devolver un arreglo dentro de otro arreglo, y hay que revisar el árbol vacío, los negativos y los decimales.
• 51:23
  PMemesPausa de memes: reclutador pidiendo años de experiencia con MCP, IA que reemplaza trabajos, el 75% de datos sintéticos en 2026, y el ataque a la librería LLM de Python, con unos 97 millones de descargas, envenenada para robar credenciales. Mencionan repositorios curados de librerías, como el servicio de Anaconda.
• 59:10
  Chris sufriendoRodo se ausenta a preparar leche para su hija y Cris queda a cargo del chat. Reconoce que le cuesta hablar solo al aire, y Rodo da la pista de que el problema se resuelve con BFS.
• 01:00:24
  Solución Level Order BFSSe usa una cola (`deque` de `collections`) y no hace falta un arreglo de visitados, porque en un árbol hay un solo camino a cada nodo y no hay ciclos. Cada ciclo del `while` calcula el tamaño del nivel, saca con `popleft`, guarda los valores y agrega primero el hijo izquierdo y luego el derecho. Maneja la raíz nula como caso borde.
• 01:06:42
  Qué es DFSDepth First Search prioriza la profundidad: se elige un camino hasta el final, se retrocede un paso y se prueba la siguiente alternativa. Se repite hasta cubrir el árbol.
• 01:08:15
  Problema Number of IslandsContar islas en una grilla de unos (tierra) y ceros (agua) equivale a contar las componentes conexas de un grafo. Rodo dice que le salió en una entrevista. Solo importan las conexiones entre unos, y en el ejemplo hay tres islas.
• 01:13:19
  Intuición DFS en la grillaSe parte de un punto cualquiera y se descartan los ceros. Al encontrar un uno se recorren sus vecinos hasta cerrar la isla, y se suma una isla al contador. Mientras Rodo no está, comentan la presentación de Terafab de Elon Musk y la frase de Jensen Huang sobre gastar la mitad del sueldo en tokens. También prueban si un LLM cuenta bien las islas de la foto.
• 01:18:48
  Código DFS con visitadosRevisa la grilla vacía, las dimensiones y un `set` de visitados con búsqueda en O(1). La función `dfs(fila, col)` valida límites, visitados y agua, marca la celda y se llama recursivamente en las cuatro direcciones (arriba, abajo, izquierda, derecha). El bucle principal recorre toda la matriz y suma una isla por cada uno no visitado.
• 01:24:39
  Asegurarse de no tener recursión con bucles infinitosLos casos borde y el conjunto de visitados evitan la recursión infinita. La función no devuelve nada útil porque lo que interesa es el conteo. Cris sigue el flujo de las llamadas recursivas y Rodo explica cómo se resuelven.
• 01:29:10
  CierreCris dice que le da esperanza ver que los problemas se resuelven con for, while e if, de forma eficiente y sin repetirse. Rodo anuncia un próximo episodio sobre buenas prácticas de entrevista y dice que los algoritmos vistos cubren cerca del 80% de los problemas típicos. Agradece a quienes se suscribieron y recuerda el horario de los martes.

Palabras clave