Motivation
Lección 2 de 9 del curso Búsqueda en profundidad - Algoritmos de grafos de Coddy.
DFS explora un grafo comprometiéndose con un camino y siguiéndolo hasta donde llega, para luego retroceder hasta el último vértice con un vecino no explorado.
¿Por qué aprender DFS?
- Fundamental: es la base de la detección de ciclos, el ordenamiento topológico, los componentes conectados y muchos otros algoritmos.
- Simple y económico: se ejecuta en tiempo O(V + E) utilizando una pila (o recursión) y un marcador de visitado.
- Versátil: el mismo recorrido responde a preguntas como "¿están conectados estos dos vértices?" y "¿cuántas piezas separadas tiene el grafo?".
Para que los resultados sean predecibles, siempre visitamos los vecinos de un vértice en orden ascendente.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
