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?
Otras formas de programar DFS
8/52Lectura
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:
...
Regístrate o inicia sesión para leer el resto del contenido.
Aportes 2
Preguntas 0
/* 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
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?
o inicia sesión.