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

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

6/52
Recursos

Aportes 5

Preguntas 0

Ordenar por:

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

En este video hay una buena explicación: video

DFS (Depth-First Search) y BFS (Breadth-First Search) son dos algoritmos para recorrer o buscar en un grafo.

La principal diferencia entre DFS y BFS es la estrategia que se sigue para recorrer el grafo. DFS sigue una estrategia de profundidad, es decir, explora lo más profundo posible en cada rama antes de retroceder. En cambio, BFS sigue una estrategia de amplitud, es decir, explora todos los nudos a la misma profundidad antes de pasar a la siguiente profundidad.

Algunas diferencias más específicas entre DFS y BFS:

Orden de visita: En DFS, los nodos se visitan en el orden en que se encuentran en la rama actual. En BFS, los nodos se visitan en orden de cercanía a la fuente, es decir, primero se visitan todos los nodos adyacentes al nodo fuente, luego los nodos adyacentes a esos nodos, y así sucesivamente.

Memoria: En general, BFS tiende a utilizar más memoria que DFS debido a que necesita almacenar todos los nodos adjuntos en cada nivel antes de avanzar al siguiente nivel. DFS solo necesita almacenar los nodos en la pila o en la llamada recursiva actual.

Aplicaciones: DFS se utiliza normalmente para encontrar componentes conectados en un grafo, encontrar ciclos en un grafo, y ordenamiento topológico. BFS se utiliza habitualmente para encontrar el camino más corto entre dos nodos en un grafo, búsqueda de elementos en un árbol o grafo, y para realizar un recorrido completo del grafo.

Estas son mis notas de la clase(https://www.notion.so/C-06-An-lisis-de-DFS-algoritmo-de-b-squeda-en-profundidad-78e94fcf6500482690a7d0abdd055e76): ![](https://static.platzi.com/media/user_upload/image-7e49f4c1-7045-4754-8a34-27db6497d4a8.jpg)
dado a que la explicacion de DFS no fue muy detallada, aqui mi aporte: Una búsqueda en profundidad (DFS) es un algoritmo de búsqueda para lo cual recorre los nodos de un grafo. Su funcionamiento consiste en ir expandiendo cada uno de los nodos que va localizando, de forma recurrente (desde el nodo padre hacia el nodo hijo). El algoritmo de búsqueda en profundidad tienes varias aplicaciones, entre las cuales tenemos las siguientes: * Encontrar nodos conectados en un grafo * Ordenamiento topológico en un grafo acíclico dirigido * Encontrar puentes en un grafo de nodos * Resolver puzzles con una sola solución, como los laberintos * Encontrar nodos fuertemente conectados

Como en los videojuegos de deciciones donde según el camino que decidas sera diferente el reto.