A este punto sería bueno hacer un ejemplo práctica para entender mejor el tema.
Introducción
¿Qué es un grafo?
¿Qué es un árbol?
¿Qué es recursión?
Aplicaciones reales de grafos y árboles
Formas de representar un grafo
DFS
Análisis de DFS: algoritmo de búsqueda en profundidad
Programando DFS de forma recursiva
Otras formas de programar DFS
Recorridos y profundidad de un Árbol
Sum Root to Leaf Numbers: análisis del problema
Solución de Sum Root to Leaf Numbers
Playground: Sum Root to Leaf Numbers
Programando Sum Root to Leaf Numbers en Golang
Number of Islands: análisis del problema
Solución de Number of Islands
Playground: Number of Islands
Programando Number of Islands en Python
Ejercicios recomendados de DFS
Ejercicios resueltos de DFS
BFS
Análisis de BFS: algoritmo de búsqueda en anchura
Programando BFS con Python
Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema
Solución de Minimum Knights Moves
Playground: Minimum Knights Moves
Programando Minimum Knights Moves con Python
Rotting Oranges: análisis del problema
Solución de Rotting Oranges
Playground: Rotting Oranges
Rotting Oranges con Java
Shortest Bridge Between Islands: análisis del problema
Solución de Shortest Bridge Between Islands
Playground: Shortest Bridge Between Islands
Programando Shortest Bridge Between Islands con Python
Ejercicios recomendados de BFS
Ejercicios resueltos de BFS
Backtrack
Algoritmo de Backtrack
Letter Combinations of a Phone Number: análisis del problema
Solución de Letter Combinations of a Phone Number
Programando Letter Combinations of a Phone Number con C++
Playground: Letter Combinations of a Phone Number
Restore IP Addresses: análisis del problema
Programando Restore IP Addresses con C++
Playground: Restore IP Addresses
Word Search: análisis del problema
Solución de Word Search
Playgrund: Word Search
Programando Word Search JavaScript
Reto: N Queens Puzzle
Ejercicios recomendados de Backtrack
Ejercicios resueltos de Backtrack
Próximos pasos
¿Qué otros algoritmos y tipos de grafos puedes aprender?
¿Quieres más cursos avanzados de algoritmos?
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Si ya tienes una cuenta,
No se trata de lo que quieres comprar, sino de quién quieres ser. Aprovecha el precio especial.
Antes: $249
$209
Paga en 4 cuotas sin intereses
Termina en:
13 Días
12 Hrs
6 Min
49 Seg
Programando DFS de forma recursiva
7/52Recursos
Aportes 11
Preguntas 1
Ordenar por:
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
Es de los cursos con menos comentarios que he visto y es de los temas mas importantes, pero uno no se da cuenta de eso hasta que deja de intentar de aprender los 100 lenguajes que existen y se da cuenta que solo hay que aprender las bases y la sintaxis no es tan importante, que paradoja
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).
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:
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)
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?