Programando DFS

Curso de Algoritmos Avanzados: Grafos y Árboles

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?

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 4

Preguntas 0

Ordenar por:

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

Clever Serrano H

hace 2 años

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

Bryan David

hace 18 días

My Little DFS with Stack as aux DS \n ```js /* 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 \*/ /\* 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);

Hector Hugo Vinasco Amaya

hace 10 meses

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

Samuel Luis Mendoza

hace 2 años

/* 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