Materia: #técnicas_y_diseños_de_algoritmos

Tags: Algoritmo, Arboles, Grafos, Dígrafos

DFS

En Ciencias de la Computación, DFS (Depth First Search) es un algoritmo de búsqueda no informada utilizado para recorrer todos los nodos de un árbol, grafo o dígrafo. Comenzando desde algún nodo, se explora cada rama lo más profundo posible antes de retroceder y evaluar otros caminos. Es un enfoque similar al backtracking, pero en lugar de detenerse cuando "se equivoco" se detiene cuando físicamente ya no puede avanzar mas.

flowchart TD

id1((1))
id2((2))
id3((7))
id4((8))
id5((3))
id6((6))
id7((9))
id8((12))
id9((4))
id10((5))
id11((10))
id12((11))

id1 --- id2
id1 --- id3
id1 --- id4
id2 --- id5
id2 --- id6
id4 --- id7
id4 --- id8
id5 --- id9
id5 --- id10
id7 --- id11
id7 --- id12

En este dibujo se puede ver el orden en el que son visitados los nodos si se corre el algoritmo desde la raíz.

Pseudocódigo

DFS(Grafo, raiz):
	porVisitar = {raiz};
	contador = 0;
	ordenDeBusqueda[contador] = {raiz}
	while (porVisitar no este vacia) do:
		actual = porVisitar.pop();
		if (existe un camino a un nodo N que no se encuentre en porVisitar) do:
			porVisitar = porVisitar.push(N);
			contador = contador + 1;
			ordenDeBusqueda[contador] = actual;
		else:
			porVisitar = porVisitar - {actual};
		end if;
	end while;
	return ordenDeBusqueda;

En este pseucódigo devolvemos la lista del orden en que fueron visitados los nodos, pero podríamos buscar otra información.

Complejidad

Este algoritmo tiene una complejidad temporal de $O(|V|+|E|)$. Podemos pensar que en el peor caso, se llega a recorrer el grafo completo.

Por otro lado, en términos de memoria, y sin contar el espacio del propio grafo, necesitaríamos como mucho $O(|V|)$, ya que lo único que estamos guardando en el proceso es los nodos que no visitamos. En el peor caso, un nodo conecta con todos los demás, y la lista tiene todos los vértices.

Usos

Los algoritmos que implementan DFS suele ser usado para:

• Detección de ciclos, en el caso de ser un dígrafo.

• Ordenar los nodos de acuerdo a algún valor ordenable que cada uno tenga.

• Determinar las componentes fuertemente conexas de un dígrafo.

• Determinar los puntos de corte y las aristas puente de un grafo.