Cápsula DFS 2024-1

Deep First Search. Resolución de ejercicio de interrogación pasada como parte del repaso I2 de la versión 2024-1 del curso Estructura de Datos y Algoritmos.

Fe de Erratas: Sobre la complejidad se menciona que DFS al terminar con todos los hijos de un nodo padre, este sube al padre por lo que agregar la comparativa de min{} no añade complejidad. Lo anterior es verdad pero corrijo lo siguiente. El recorrido de DFS es lo que indica el stack y no es que se pasea por el padre para llegar a cada hijo (lo que digo en min 29:30). Para propagar el valor w.low hacia los padres, en cada nodo hijo (que sea este un grafo también bidireccional ayuda) podemos hacer una operación O(1) donde cada nodo consulte el nodo por dónde recién llegó (ancestro) y ahí subir el valor w,low para evaluarlo en dicho padre y encontrar el u.low momentáneo.