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

Clase 8 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

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

Clever Serrano H

student•

https://www.youtube.com/watch?v=iE8m53SxhDc

José Ramón García

student•

Comparto código en python con ejemplo de grafo

class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.adj_list[u] = []
        if v not in self.adj_list:
            self.adj_list[v] = []
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

def dfs_iterative_search(grafo, inicio, valorAEncontrar):
    stack = [inicio]  # Usamos una pila para el DFS
    visited = set()  # Conjunto para evitar ciclos

    while stack:
        node = stack.pop() 
        if node in visited:
            continue  

        print(f"Visiting Node {node}")
        visited.add(node)

        if node == valorAEncontrar:
            print(f"Hemos encontrado el nodo {valorAEncontrar}!")
            return node

        #(en orden inverso para mantener consistencia con DFS recursivo)
        for hijos in reversed(grafo.get(node, [])):
            if hijos not in visited:
                stack.append(hijos)
    print("Nodo no encontrado.")
    return None

Platzi Team

student••

module Grafos
  class DfsService
    attr_reader :graph

    def initialize(graph)
      @graph = graph
    end

    # DFS recursivo
    def run_recursive(start)
      visited = {}
      dfs_rec(start, visited)
      visited.keys
    end

    # DFS iterativo con pila
    def run_iterative(start)
      visited = {}
      stack = [start]

      until stack.empty?
        node = stack.pop
        next if visited[node]

        visited[node] = true

        graph[node].each do |neighbor|
          stack << neighbor unless visited[neighbor]
        end
      end

      visited.keys
    end

    private

    def dfs_rec(node, visited)
      return if visited[node]

      visited[node] = true

      graph[node].each do |neighbor|
        dfs_rec(neighbor, visited)
      end
    end
  end
end

Mario Alberto Hernández Pintor

student•

// 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);

Bryan Castano

student•

My Little DFS with Stack as aux DS \n

/* DEPTH FIRST SEARCH AS DFS */ 
/* GRAPH TRAVERSAL BY USING STACK AS DSA */
/* VISITED ARRAY AS AUX LIST TO HANDLE VISITED NODES
AVOID VISIT VERTICES MULTIPLE TIME AS LOOP */ 

const V = 5;

function dfs(arr, source) {

  var mstack = [];
  
  var isVisited = Array(V).fill(false);

  mstack.push(source);
  
  isVisited[source] = true;

  while (mstack.length) {
  
    var node = mstack.pop();
    
    document.write("Visited Node: " + node);

    for (var index = 0; index < V; index++) {
    
      if (arr[node][index] === 1 && isVisited[index] === false) {
      
        mstack.push(index);
        
        isVisited[index] = true;
        
      }
      
    }
    
  }
  
}

// ADJ MATRIX OF GRAPH TRAVERSAL BY DFS ALGORITHM ...

var arr = [  
             [0, 1, 1, 1, 0],
  	     [1, 0, 0, 1, 1],
             [1, 0, 0, 1, 0],
             [1, 1, 1, 0, 1],
             [0, 1, 0, 1, 0]
          ];

document.write("DFS of the given graph is : ");


dfs(arr, 0);



```/\* DEPTH FIRST SEARCH AS DFS \*/&#x20;

/\* GRAPH TRAVERSAL BY USING STACK AS DSA \*/

/\* VISITED ARRAY AS AUX LIST TO HANDLE VISITED NODES

AVOID VISIT VERTICES MULTIPLE TIME AS LOOP \*/&#x20;



const V = 5;



function dfs(arr, source) {



&#x20; var mstack = \[];

&#x20;&#x20;

&#x20; var isVisited = Array(V).fill(false);



&#x20; mstack.push(source);

&#x20;&#x20;

&#x20; isVisited\[source] = true;



&#x20; while (mstack.length) {

&#x20;&#x20;

&#x20;   var node = mstack.pop();

&#x20;  &#x20;

&#x20;   document.write("Visited Node: " + node);



&#x20;   for (var index = 0; index < V; index++) {

&#x20;  &#x20;

&#x20;     if (arr\[node]\[index] === 1 && isVisited\[index] === false) {

&#x20;    &#x20;

&#x20;       mstack.push(index);

&#x20;      &#x20;

&#x20;       isVisited\[index] = true;

&#x20;      &#x20;

&#x20;     }

&#x20;    &#x20;

&#x20;   }

&#x20;  &#x20;

&#x20; }

&#x20;&#x20;

}



// ADJ MATRIX OF GRAPH TRAVERSAL BY DFS ALGORITHM ...



var arr = \[ &#x20;

&#x20;            \[0, 1, 1, 1, 0],

&#x20; 	     \[1, 0, 0, 1, 1],

&#x20;            \[1, 0, 0, 1, 0],

&#x20;            \[1, 1, 1, 0, 1],

&#x20;            \[0, 1, 0, 1, 0]

&#x20;         ];



document.write("DFS of the given graph is : ");





dfs(arr, 0);

Hector Hugo Vinasco Amaya

student•

Estos cursos están muy mal organizados, uno viene de ver fundamentos de algoritmos y llega aquí y no entiende nada, ella dice que hay un curso antes de este pero no se sabe cual es, deberían hacer una ruta solo de algoritmos que uno sepa cual seguir para no perderse, yo la verdad ya me desmotive y siento que enterré mi plata con platzi

Santiago Amaya

student•

Es un curso avanzado... te recomiendan conocimientos previos de estructura de datos y que comprendas sintaxis de dos lenguajes de programación... en mi caso solo se python, Eh disfrutado mucho el curso, tu disgusto es:

te falta practica haciendo estructura de datos.
Ser auto solvente con las herramientas de internet para aprender.
No quedarte solo con el video hay libros, videos y chat gpt3 que te pueden ayudar.
en mi perspectiva el curso esta a nivel de pregrado, y esta diseñado para desarrollar un pensamiento algorítmico (te enseña a pensar) si te cuesta es por que no has aprendido a pensar algorítmicamente por lo cual creo que puedes tomar cursos menos difíciles

YOVANA FLOREZ CHOQUE

student•

No es tu culpa Hector, realmente ensena muy mal!

Samuel Luis Mendoza

student•

/* DFS: Depth First Search - Búsqueda en profundidad */

/* DFS boolean true or false */
const dfsb = function (root, target) {
    if (!root) return false;
    if (root.value === target) return true;
    return dfsb(root.left, target) || dfsb(root.right, target);
}

/* DFS node or null */
const dfsn = function (root, target) {
    if (!root) return null;
    if (root.value === target) return root;
    return dfsn(root.left, target) || dfsn(root.right, target);
}

const root = {
    value: 1,
    left: {
        value: 2,
        left: {
            value: 4,
            left: null,
            right: null
        },
        right: {
            value: 5,
            left: null,
            right: null
        }
    },
    right: {
        value: 3,
        left: {
            value: 6,
            left: null,
            right: null
        },
        right: {
            value: 7,
            left: null,
            right: null
        }
    }
}

console.log(dfsn(root, 5)); // { value: 5, left: null, right: null }
console.log(dfsn(root, 8)); // null

console.log(dfsb(root, 5, true)); // true
console.log(dfsb(root, 8, true)); // false

Jared Flores Martinez

student•

graph = [

{

"node": "A",

"adyacent": ["B", "C"],

"Father": None

{

"node": "B",

"adyacent": ["D"],

"Father": None

{

"node": "C",

"adyacent": ["B"],

"Father": None

{

"node": "D",

"adyacent": ["C"],

"Father": None

}

]

visited = []

def searchNode(graph, node_name):

for node in graph:

if node["node"] == node_name:

return node

return None

def dfs(initialGraph, root):

visited.append(root.get("node"))

for vertex in root["adyacent"]:

if (vertex not in visited):

vertex = searchNode(graph, vertex)

vertex["Father"] = root["node"]

dfs(initialGraph, vertex)

dfs(graph, graph[0])

graph = [
    {
        "node": "A",
        "adyacent": ["B", "C"],
        "Father": None
    },
    {
        "node": "B",
        "adyacent": ["D"],
        "Father": None
    },
    {
        "node": "C",
        "adyacent": ["B"],
        "Father": None
    },
    {
        "node": "D",
        "adyacent": ["C"],
        "Father": None
    }
]

visited = []

def searchNode(graph, node_name):
    for node in graph:
        if node["node"] == node_name:
            return node
    
    return None

def dfs(initialGraph, root):
    visited.append(root.get("node"))

    for vertex in root["adyacent"]:
        if (vertex not in visited):
            vertex = searchNode(graph, vertex)
            vertex["Father"] = root["node"]
            dfs(initialGraph, vertex)

dfs(graph, graph[0])

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

Introducción

Grafos y Árboles: Estructuras de Datos Avanzadas

Estructuras de Datos: Introducción a Árboles y Sus Propiedades

Recursión: Concepto y Aplicaciones Prácticas con Ejemplos

Aplicaciones Prácticas de Grafos en Tecnología e Industria

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Búsqueda en Profundidad (DFS) en Árboles y Grafos

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

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

Recorridos y Profundidad en Árboles Binarios y Enearios

Suma de Caminos en Árboles Binarios

Suma de Números de Raíz a Hoja en Árboles

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Resolución del Problema de Número de Islas con DFS

Conteo de Islas en Matrices con DFS

Playground: Number of Islands

Implementación de "Número de Islas" con Recursión en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles

Implementación de BFS en Árboles usando Python

Movimiento mínimo de caballo en ajedrez infinito

Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Propagación de Plagas en Matrices usando BFS en Java

Construcción de Puentes Cortos entre Islas en Matrices Binarias

Resolución del Problema Shortest Bridge con DFS y BFS

Playground: Shortest Bridge Between Islands

Búsqueda del camino más corto entre islas usando BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Algoritmo Backtracking: Solución de Problemas Complejos

Combinaciones de Letras en Números Telefónicos

Combinaciones de Letras a partir de un Número de Teléfono

Generación de combinaciones de letras con teclados numéricos en C++

Playground: Letter Combinations of a Phone Number

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Generación de IPs válidas con backtracking en C++

Playground: Restore IP Addresses

Búsqueda de Palabras en Matrices: Solución y Complejidad

Búsqueda de Palabras en Matrices usando Backtracking y DFS

Playgrund: Word Search

Implementación de búsqueda de palabras en matrices con DFS en JavaScript

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Algoritmos de Grafos: MIN/MAX-HIP, TRI, Topological Sort y Dijkstra

Algoritmos y Estructuras de Datos en la Ingeniería