Introducción

1

¿Qué es un grafo?

2

¿Qué es un árbol?

3

¿Qué es recursión?

4

Aplicaciones reales de grafos y árboles

5

Formas de representar un grafo

DFS

6

Análisis de DFS: algoritmo de búsqueda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un Árbol

10

Sum Root to Leaf Numbers: análisis del problema

11

Solución de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: análisis del problema

15

Solución de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

Análisis de BFS: algoritmo de búsqueda en anchura

21

Programando BFS con Python

22

Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema

23

Solución de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: análisis del problema

27

Solución de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: análisis del problema

31

Solución de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

Letter Combinations of a Phone Number: análisis del problema

38

Solución de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: análisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: análisis del problema

45

Solución de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Próximos pasos

51

¿Qué otros algoritmos y tipos de grafos puedes aprender?

52

¿Quieres más cursos avanzados de algoritmos?

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Programando DFS de forma recursiva

7/52
Recursos

Aportes 10

Preguntas 1

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

A este punto sería bueno hacer un ejemplo práctica para entender mejor el tema.

Hola 😄, pueden probar el código con el siguiente árbol de ejemplo.
.

.
dfsBin.js:

const dfs = function (raiz, valorAEncontrar) {
  if (!raiz) {
    // si raiz es null o undefined, termina la función
    return null;
  }

  console.log("En este momento estoy en el nodo, el valor " + raiz.valor);
  if (raiz.valor === valorAEncontrar) {
    console.log("Econtré el valor!!! ");
    return raiz;
  }

  var izquierda = dfs(raiz.izquierda, valorAEncontrar);
  var derecha = dfs(raiz.derecha, valorAEncontrar);
  if (izquierda != null) {
    return izquierda;
  }
  if (derecha != null) {
    return derecha;
  }

  return null;
};

//Creación del árbol como objeto
let nodos = {
  valor: 25,
  izquierda: {
    valor: 10,
    izquierda: {
      valor: 8,
      izquierda: {
        valor: 6,
        izquierda: {
          valor: 1,
          izquierda: null,
          derecha: null,
        },
        derecha: {
          valor: 7,
          izquierda: null,
          derecha: null,
        },
      },
      derecha: null,
    },
    derecha: {
      valor: 13,
      izquierda: null,
      derecha: {
        valor: 15,
        izquierda: null,
        derecha: null,
      },
    },
  },
  derecha: {
    valor: 40,
    izquierda: {
      valor: 30,
      izquierda: {
        valor: 26,
        izquierda: null,
        derecha: null,
      },
      derecha: null,
    },
    derecha: {
      valor: 42,
      izquierda: null,
      derecha: {
        valor: 49,
        izquierda: {
          valor: 45,
          izquierda: null,
          derecha: null,
        },
        derecha: {
          valor: 51,
          izquierda: null,
          derecha: null,
        },
      },
    },
  },
};

// Probar la función dfs
let nodoEncontrado = dfs(nodos, 30);
console.log("\nEl valor encontrado es:\n");
console.log(nodoEncontrado);

.
Pueden ejecutarlo por la terminal, desde el directorio donde tienen guardado el archivo, ejecutando:

node dfsBin.js

Seria bueno en este caso, mostrar como es el objeto que se va a recorrer con eso queda un poco ilulstrado

este algoritmo tal cual está implementado terminará lanzando un error en el caso que el valor objetivo no esté dentro del grafo. Es tan importante definir el caso bueno (valor encontrado) como el malo (valor no encontrado). Se puede validar tanto si "raiz" es null, como "raiz.left" y "raiz.right" son null (prefiero esta segunda opción). . Además creo que el uso del término "raiz" es incorrecto/confuso, ya que la raiz hace referencia al nodo raiz del grafo. Aunque podemos debatir sobre si consideramos cada iteración un subgrafo (por lo que raiz sería correcto), creo que es mejor llamarlo "padre".

Estaria bueno primero tener un video de como es la estructura de una grafo, como se implementa, que propiedades y metodos tiene para entender mejor el algoritmo

así sería el recorrido en alrbol binario, a la izquierda BFS y a la derecha DFS ![](https://static.platzi.com/media/user_upload/image-50b4ea0f-6c0f-49e3-80b9-68822b52e9d1.jpg)
Siguiendo el ejemplo de un arbol con valores númericos me aborde a implementar DFS en go (dado que es un lenguaje que estoy aprendiendo), así que les comparto el codigo que realice (blob:https://app.codeimage.dev/30f31b71-b4b5-4414-af95-195c11d9b256). ![](https://static.platzi.com/media/user_upload/image-69fabf28-dba8-47ca-a539-6e8e25aadfcc.jpg)
hice este código en java creando la clase Nodo\<T> donde se pueden agregar los hijos en una lista, su valor y el valor del padre (por si acaso xd) ```java public class DFS { public static void main(String[] args) { System.out.println("********** DFS ***********"); Nodo<Integer> head = prepareHead(); System.out.println("ingrese el valor del nodo a buscar"); Scanner sc = new Scanner(System.in); int valorABuscar = sc.nextInt(); System.out.printf("valor [%s] encontrado: %b\n", valorABuscar, buscarNodo(head, valorABuscar) != null); } private static Nodo<Integer> buscarNodo(Nodo<Integer> head, int valorABuscar) { System.out.printf("buscando valor [%d] en nodo con valor [%d]\n", valorABuscar, head.valor); if(head.valor == valorABuscar){ return head; } if(head.hijos != null) { for (Nodo<Integer> hijo : head.hijos) { Nodo<Integer> resultado = buscarNodo(hijo, valorABuscar); if (resultado != null && resultado.valor.equals(valorABuscar)) { return resultado; } } } return null; } private static Nodo<Integer> prepareHead() { Nodo<Integer> cabeza = new Nodo<>(1); Nodo<Integer> hijo1 = new Nodo<>(2, cabeza); Nodo<Integer> hijo2 = new Nodo<>(3, cabeza); Nodo<Integer> hijo3 = new Nodo<>(4, cabeza); cabeza.hijos = (Arrays.asList(hijo1, hijo2, hijo3)); Nodo<Integer> nieto1 = new Nodo<>(5, hijo1); Nodo<Integer> nieto2 = new Nodo<>(6, hijo1); Nodo<Integer> nieto3 = new Nodo<>(7, hijo1); hijo1.hijos = (Arrays.asList(nieto1, nieto2, nieto3)); Nodo<Integer> nieto4 = new Nodo<>(8, hijo2); Nodo<Integer> nieto5 = new Nodo<>(9, hijo2); Nodo<Integer> nieto6 = new Nodo<>(10, hijo2); hijo2.hijos = (Arrays.asList(nieto4, nieto5, nieto6)); Nodo<Integer> nieto7 = new Nodo<>(11, hijo3); Nodo<Integer> nieto8 = new Nodo<>(12, hijo3); Nodo<Integer> nieto9 = new Nodo<>(13, hijo3); hijo3.hijos = (Arrays.asList(nieto7, nieto8, nieto9)); return cabeza; } static class Nodo<T> { T valor; Nodo<T> padre; List<Nodo<T>> hijos; public Nodo(T valor) { this.valor = valor; } public Nodo(T valor, Nodo<T> padre) { this.valor = valor; this.padre = padre; } } } ```
tengo un poco de dudas de como implemetar el nodo en JS porque no es mi fuerte, pero esa es la idea porque en Jav sin problamas ya lo implemete: ![](https://static.platzi.com/media/user_upload/image-a5dd6816-e65a-44b9-a43c-3cfb3e2ce097.jpg) Este es el link de l repo(https://github.com/Dani-Ideas/DFS\_JS)
# Función para realizar DFS en un grafo dado
def dfs(graph, node, visited):
    # Marcar el nodo actual como visitado
    visited[node] = True
    print("Visitando nodo:", node)

    # Recorrer todos los nodos adyacentes al nodo actual
    for neighbor in graph[node]:
        if not visited[neighbor]:
            # Si el vecino no ha sido visitado, realizar DFS en él
            dfs(graph, neighbor, visited)


# Ejemplo de uso
if __name__ == "__main__":
    # Grafo representado como listas de adyacencia
    graph = {
        0: [1, 2],
        1: [0, 3, 4],
        2: [0, 5],
        3: [1],
        4: [1],
        5: [2]
    }

    # Inicializar un arreglo para llevar un seguimiento de los nodos visitados
    visited = [False] * len(graph)

    # Realizar DFS desde el nodo 0
    dfs(graph, 0, visited)