DFS

DFS, acrónimo para Depth-First Search, en español Búsqueda en Profundidad, es un algoritmo usado para procesar grafos, una búsqueda tal como lo describe el nombre. La idea es que se toma como prioridad en la búsqueda la profundidad del nodo. Para demostrarlo, el siguiente grafo presenta como contenido de los nodos, el índice en el cual es procesado.

En general, se comienza desde el nodo madre, y de ahí se sigue con su primer hijo, si hay. Luego se realiza lo mismo con este último nodo. Después se sigue con su siguiente hijo, si hay, y de ahí volvemos al nodo superior…

Pero ahora ¿cómo procesamos este grafo?, en el ejemplo, tenemos acceso al nodo n° 1 y queremos acceder a los subyacentes, pero en cada uno de ellos, tenemos como prioridad sus hijos, etc. Bueno, ciertos lenguajes nos ofrecen estructuras de datos para manejar esta situación, tal es el caso de C++, en donde nos provee la clase de STL, stack, la cual sigue una funcionalidad LIFO (last-in, first-out) ingles para el último que entra, primero que sale, y como se nota es lo que necesitamos. Los últimos nodos que nos encontramos son los primeros que vamos a procesar…

Entonces, las funciones que nos ofrece stack son, siento T el tipo de datos que representa a los nodos:

bool empty();

Indica si quedan más elementos en la clase.

void pop();

Elimina el último elemento de la clase.

void push(const T& val);

Añade un elemento al final de la clase.

T & top() const;

Retorna el último elemento de la clase.

En aplicación, digamos el siguiente caso:

#include <stack>
using namespace std;

// Sea 'node' la estructura que representa cada nodo

void dfs(node & n) {
	stack<node> v;

	// Añadimos el nodo principal en 'v'
	v.push(n);

	// Verificamos de que queden elementos en 'v'
	while (!v.empty()) {
		// Accedemos al último elemento
		m = v.top();
		// procesamos 'm'...

		// Ahora luego de procesado, lo quitamos de 'v'.
		v.pop();

		// Añadimos los hijos del nodo 'm', si los hay, ejemplo:
		// v.push(m.Children(1));
	}

	// Al llegar aquí ya hemos procesado todos los elementos...
}

Un caso particular de DFS son ciertas clases de funciones recursivas. Un patrón común seria el siguiente:

void dfs(node & n) {
	int m; // Sea 'm' la cantidad de elementos del nodo 'n'

	// procesamos 'n'...

	for (i = 0; i < m; ++i) {
		// seguido, mandamos a procesar cada elemento subyacente de 'n', ejemplo:
		// dfs(n.Children(i));
	}
}

De todos modos, podemos usar la clase stack para evitar la recursividad si es requerido.

Este tipo de algoritmos se pueden encontrar en la red, pero por lo general son dificiles de entender, en este caso trato de que sea lo más facil posible siempre y cuando se tenga un conocimiento de grafos, para cualquier duda o corrección estan los comentarios.

• 

Posts Relacionados

• Solución a ¿Cuántas formas? Primero, no importan que caracteres son, con o da la...
• Balanceo de expresiones usando pilas en c++ Buenas El balanceo de expresiones (no se con que otro...
• Balanceo de expresiones II Buenas. Ayer en este post hablabamos de balanceo de expresiones...