Búsqueda en Profundidad

La búsqueda en profundidad (DFS) es uno de los algoritmos principales sobre grafos.

La búsqueda en profundidad encuentra el camino lexicográficamente primero en el grafo desde un vértice fuente $u$ hasta cada vértice. La búsqueda en profundidad también encontrará los caminos más cortos en un árbol (porque solo existe un camino simple), pero en grafos generales esto no es así.

El algoritmo trabaja en tiempo $O(m + n)$ , donde $n$ es la cantidad de vértices y $m$ es la cantidad de aristas.

Descripción del algoritmo

La idea detrás de DFS es ir tan profundo como sea posible en el grafo, y hacer backtracking una vez que se está en un vértice sin vértices adyacentes no visitados.

Es muy fácil describir / implementar el algoritmo de forma recursiva: Empezamos la búsqueda en un vértice. Después de visitar un vértice, hacemos además un DFS para cada vértice adyacente que todavía no hayamos visitado. De esta forma visitamos todos los vértices alcanzables desde el vértice de inicio.

Para más detalles, consultar la implementación.

Aplicaciones de la Búsqueda en Profundidad

Encontrar cualquier camino en el grafo desde el vértice fuente $u$ hasta todos los vértices.
Encontrar el camino lexicográficamente primero en el grafo desde la fuente $u$ hasta todos los vértices.
Comprobar si un vértice de un árbol es ancestro de algún otro vértice:

Al comienzo y al final de cada llamada de búsqueda recordamos el “tiempo” de entrada y de salida de cada vértice. Ahora se puede encontrar la respuesta para cualquier par de vértices $(i, j)$ en $O(1)$ : el vértice $i$ es ancestro del vértice $j$ si y solo si $\text{entry}[i] < \text{entry}[j]$ y $\text{exit}[i] > \text{exit}[j]$ .
Encontrar el ancestro común más bajo (LCA) de dos vértices.
Orden topológico:

Correr una serie de búsquedas en profundidad de modo de visitar cada vértice exactamente una vez en tiempo $O(n + m)$ . El orden topológico pedido serán los vértices ordenados de forma descendente por tiempo de salida.
Comprobar si un grafo dado es acíclico y encontrar ciclos en un grafo. (Como se menciona más abajo, contando las aristas de retroceso en cada componente conexa).
Encontrar componentes fuertemente conexas en un grafo dirigido:

Primero hacer un orden topológico del grafo. Después transponer el grafo y correr otra serie de búsquedas en profundidad en el orden definido por el orden topológico. Para cada llamada a DFS, la componente creada por ella es una componente fuertemente conexa.
Encontrar puentes en un grafo no dirigido:

Primero convertir el grafo dado en un grafo dirigido corriendo una serie de búsquedas en profundidad y haciendo dirigida cada arista a medida que la recorremos, en la dirección en la que fuimos. Segundo, encontrar las componentes fuertemente conexas en este grafo dirigido. Los puentes son las aristas cuyos extremos pertenecen a distintas componentes fuertemente conexas.

Clasificación de las aristas de un grafo

Podemos clasificar las aristas de un grafo $G$ usando los tiempos de entrada y de salida de los nodos extremos $u$ y $v$ de las aristas $(u,v)$ . Estas clasificaciones se usan a menudo en problemas como encontrar puentes y encontrar puntos de articulación.

Hacemos un DFS y clasificamos las aristas encontradas usando las siguientes reglas:

Si $v$ no está visitado:

Arista de árbol (tree edge) - Si $v$ se visita después de $u$ , entonces la arista $(u,v)$ se llama arista de árbol. En otras palabras, si $v$ se visita por primera vez y $u$ se está visitando actualmente, entonces $(u,v)$ se llama arista de árbol. Estas aristas forman un árbol DFS y de ahí el nombre de aristas de árbol.

Si $v$ se visitó antes que $u$ :

Aristas de retroceso (back edges) - Si $v$ es un ancestro de $u$ , entonces la arista $(u,v)$ es una arista de retroceso. $v$ es un ancestro exactamente si ya entramos a $v$ , pero todavía no salimos de él. Las aristas de retroceso completan un ciclo, ya que hay un camino del ancestro $v$ al descendiente $u$ (en la recursión de DFS) y una arista del descendiente $u$ al ancestro $v$ (arista de retroceso); así se forma un ciclo. Los ciclos se pueden detectar usando aristas de retroceso.
Aristas hacia adelante (forward edges) - Si $v$ es un descendiente de $u$ , entonces la arista $(u, v)$ es una arista hacia adelante. En otras palabras, si ya visitamos y salimos de $v$ y $\text{entry}[u] < \text{entry}[v]$ , entonces la arista $(u,v)$ forma una arista hacia adelante.
Aristas cruzadas (cross edges): si $v$ no es ni ancestro ni descendiente de $u$ , entonces la arista $(u, v)$ es una arista cruzada. En otras palabras, si ya visitamos y salimos de $v$ y $\text{entry}[u] > \text{entry}[v]$ , entonces $(u,v)$ es una arista cruzada.

Teorema. Sea $G$ un grafo no dirigido. Entonces, hacer un DFS sobre $G$ clasificará cada arista encontrada como arista de árbol o arista de retroceso; es decir, las aristas hacia adelante y las aristas cruzadas solo existen en grafos dirigidos.

Supongamos que $(u,v)$ es una arista arbitraria de $G$ y, sin pérdida de generalidad, $u$ se visita antes que $v$ , es decir, $\text{entry}[u] < \text{entry}[v]$ . Como el DFS solo procesa cada arista una vez, hay solo dos formas en las que podemos procesar la arista $(u,v)$ y así clasificarla:

La primera vez que exploramos la arista $(u,v)$ es en la dirección de $u$ a $v$ . Como $\text{entry}[u] < \text{entry}[v]$ , la naturaleza recursiva del DFS implica que el nodo $v$ se explorará por completo y, por tanto, se saldrá de él antes de que podamos “volver hacia arriba en la pila de llamadas” para salir del nodo $u$ . Así, el nodo $v$ debe estar no visitado cuando el DFS explora por primera vez la arista $(u,v)$ de $u$ a $v$ , porque de lo contrario la búsqueda habría explorado $(u,v)$ de $v$ a $u$ antes de salir del nodo $v$ , ya que los nodos $u$ y $v$ son vecinos. Por lo tanto, la arista $(u,v)$ es una arista de árbol.
La primera vez que exploramos la arista $(u,v)$ es en la dirección de $v$ a $u$ . Como descubrimos el nodo $u$ antes de descubrir el nodo $v$ , y solo procesamos cada arista una vez, la única forma de explorar la arista $(u,v)$ en la dirección de $v$ a $u$ es que haya otro camino de $u$ a $v$ que no involucre la arista $(u,v)$ , haciendo así que $u$ sea un ancestro de $v$ . La arista $(u,v)$ entonces completa un ciclo, ya que va del descendiente $v$ al ancestro $u$ , del cual todavía no hemos salido. Por lo tanto, la arista $(u,v)$ es una arista de retroceso.

Como hay solo dos formas de procesar la arista $(u,v)$ , con los dos casos y sus clasificaciones resultantes esbozados arriba, hacer un DFS sobre $G$ clasificará por tanto cada arista encontrada como arista de árbol o arista de retroceso; es decir, las aristas hacia adelante y las aristas cruzadas solo existen en grafos dirigidos. Esto completa la demostración.

Implementación


vector<vector<int>> adj; // grafo representado como lista de adyacencia
int n; // cantidad de vértices
 
vector<bool> visited;
 
void dfs(int v) {
	visited[v] = true;
	for (int u : adj[v]) {
		if (!visited[u])
			dfs(u);
    }
}

Esta es la implementación más simple de la Búsqueda en Profundidad. Como se describe en las aplicaciones, puede ser útil también calcular los tiempos de entrada y de salida y el color del vértice. Colorearemos todos los vértices con el color 0 si no los hemos visitado, con el color 1 si los visitamos, y con el color 2 si ya salimos del vértice.

Aquí hay una implementación genérica que además calcula eso:


vector<vector<int>> adj; // grafo representado como lista de adyacencia
int n; // cantidad de vértices
 
vector<int> color;
 
vector<int> time_in, time_out;
int dfs_timer = 0;
 
void dfs(int v) {
	time_in[v] = dfs_timer++;
	color[v] = 1;
	for (int u : adj[v])
		if (color[u] == 0)
			dfs(u);
	color[v] = 2;
	time_out[v] = dfs_timer++;
}

Búsqueda en Profundidad

Descripción del algoritmo

Aplicaciones de la Búsqueda en Profundidad

Clasificación de las aristas de un grafo

Implementación

Problemas de práctica