DFS (abreviación de Depth-First Search, “búsqueda en profundidad”) es una técnica de recorrido de grafos.

Consiste en recorrer el grafo, guardando una lista de “nodos que tenemos que mirar”. Esta lista tiene la particularidad de que el último nodo que agregamos a la lista es el primero que vamos a mirar (por eso “en profundidad”). Es decir, vamos a ir agotando los caminos del grafo.

El algoritmo consiste en primero, meter en la lista un nodo inicial. A partir de ahí, agarrar el último nodo que agregamos a la lista, y agregar todos sus vecinos que no fueron agregados antes (es importante mirar que no hayan sido agregados antes porque si no vamos a entrar en un loop mirando los nodos infinitas veces).

Supongamos que tenemos el siguiente grafo:

Tenemos false en la variable visitado de cada nodo, y la lista de nodos para mirar está vacía: $$\begin{array}{|c|c|c|c|c} \hline F & F & F & F & F\\ \hline & & & & & \\ \end{array}$$

Ya tenemos disponible sin embargo el video y las diapositivas de una charla sobre el tema de 2015, por Melanie Sclar.