Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Una implementación estándar de DFS coloca cada vértice del gráfico en una de las dos categorías, visitado o no visitado. El objetivo del algoritmo es marcar cada vértice como visitado evitando los ciclos. En este algoritmo:

Se inicia colocando uno de los vértices del grafo en la parte superior de una pila.
Se toma el elemento superior de la pila y se añade a la lista de vértices visitados.
Se crea una lista de los nodos adyacentes a ese vértice.
Se añade los que no están en la lista de visitados a la parte superior de la pila.
Se repite los pasos 2 y 3 hasta que la pila esté vacía.

Solución recursiva:

Crear una función recursiva que tome el índice del nodo y un array visitado.
Marque el nodo actual como visitado e imprima el nodo.
Recorrer todos los nodos adyacentes y no marcados y llamar a la función recursiva con el índice del nodo adyacente.

Solución iterativa:

Primero se insertan todos los elementos en la pila y luego se hace uso de la cabeza de la pila (que es el último nodo insertado), así que el primer nodo que se maneja es el último hijo.

def dfs(raiz):
   pila = []
   visitados = set()
   pila.append(raiz)
 
   while pila: #comprueba si hay algo en la lista de tareas pendientes
       nodoActual = pila.pop() # accede al nodo siguiente
       if nodoActual not in visitados: # actualiza los nodos visitados si este nodo no habia sido visitado antes
           visitados.add(nodoActual)
       for nodo in nodoActual.nodosAdyacentes: # itera sobre los nodos adyacentes
           if nodo not in visitados:
               pila.append(nodo) # añade a la lista de tareas pendientes

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Mario Alberto Hernández Pintor

Estudiante

// CLASE NODO
class Nodo{
	constructor(valor = null){
		this.valor = valor; 
		this.hijos = []; 
	}
}

// CLASE ARBOL
/*
Para construir un arbol con raiz, con una profundidad dada y que todos
los nodos tengan el mismo número de hijos. El valor que contiene cada nodo es
su enumeracion con raiz.valor = 1 y asi sucesivamente.
*/
class Arbol{
	constructor(ramas = 2,niveles = 3){
		this.raiz = new Nodo(1,null);
        this.ramas = ramas;
        this.niveles = niveles;
        this.vertices = 0;
    }
    
    // Esta funcion se puede omitir
    obtener_numero_vertices(){
    	for(let i =0; i < this.niveles ;i++){
    		this.vertices+= this.ramas**i;
    	}
    	return this.vertices;
    }

    // Esta funcion se puede omitir
    info(){
    	console.log("Número de hijos por nodo: ", this.ramas);
    	console.log("Número de niveles de profundidad: ", this.niveles);
    	const n = this.obtener_numero_vertices();
    	console.log("Número total de nodos: ", n);
    	console.log("Número de aristas: ", n-1);
    }
    
    // La forma de crear los nodos se hace un recorrido similar al DFS

    construir_arbol(){
    	console.log("--------Creación de árbol--------:")
    	var pila = [[this.raiz, 1]];
    	var contador = 2;

        
    	while (pila.length > 0){

    		var [nodo_actual, nivel_actual] = pila.pop();
        
    		console.log("Visitando nodo: "+ nodo_actual.valor+ " (Nivel: " + nivel_actual + ")");
    		
    			if (nivel_actual < this.niveles){
    				  var siguiente_nivel = nivel_actual + 1;

    				  for (let i = 0; i < this.ramas; i++){
    		       	var nuevoNodo = new Nodo(contador);
    		       	contador++;
    		      	nodo_actual.hijos.push(nuevoNodo);

    		      	console.log("Nodo " + nuevoNodo.valor + " creado");
                pila.push([nuevoNodo, siguiente_nivel]); 
    		     }
    			
    		 }
    		
    	}
    	console.log("Se terminó de crear el árbol")
    }

     // La forma recorrer el árbol es similar al DFS
    imprimir(){
    	console.log("--------Imprimir-------:")
    	// por profundidad de derecha a izquierda
    	var pila = [this.raiz];
    	var visitados = new Set();

        
    	while (pila.length > 0){
    		var nodo_actual =  pila.pop();

    		
    		if (visitados.has(nodo_actual.valor)){
    			continue;
    		}

    		console.log("Visitando nodo: "+ nodo_actual.valor);
    		visitados.add(nodo_actual.valor)
    
       var hijos = nodo_actual.hijos;

       for (let i = 0; i < hijos.length;i++){
       	     console.log("Hijo: " + hijos[i].valor);
             pila.push(hijos[i]);
         }

    	}
    }
    // ITERATIVO
    // Deep Fisrt Search 

    busqueda(objetivo){
    	// por profundidad de derecha a izquierda
    	console.log("--------Busqueda de:" + objetivo);
    	var pila = [this.raiz];
    	var visitados = new Set();

        
    	while (pila.length > 0){
    		var nodo_actual =  pila.pop();

    		
    		if (visitados.has(nodo_actual.valor)){
    			continue;
    		}

    		visitados.add(nodo_actual.valor)

    		if (nodo_actual.valor == objetivo){
    			  console.log("Encontramos el nodo!!");
    			  return nodo_actual;
    		}
    
       var hijos = nodo_actual.hijos;

       for (let i = 0; i < hijos.length;i++){
             pila.push(hijos[i]);
         }

    	}

    	console.log("No lo encontramos");
    	return null;

    }
}

// RECURSIVO 
// Deep Fisrt Search 
// Lo que se vio en la clase
const dfs = function(raiz, valorAEncontrar){
	console.log("En este momento estoy en el nodo que tiene el valor: "+ raiz.valor);
	if(raiz.valor == valorAEncontrar){
		console.log("Encontré el valor!");
        return raiz;
	}

	for (var i = 0; i < raiz.hijos.length; i++){
		var nodoResultado  = dfs(raiz.hijos[i], valorAEncontrar);
	    if (nodoResultado!= null){
	    	return nodoResultado;
	    }
	}
	return null;
}

// Para ejecutarlo

const miarbol = new Arbol(2,4); // puedes probar con otros parámetros
miarbol.info();
miarbol.construir_arbol();
//miarbol.imprimir();
miarbol.busqueda(8);
dfs(miarbol.raiz,8);

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

Implementación de DFS recursivo para búsqueda en árboles