Actividad 10
Recorridos de Grafos
Recorrido DFS 0 Búsqueda en Profundidad
Un Recorrido en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo. Es una generalización del recorrido preorden de un árbol.
La estrategia consiste en partir de un vértice determinado v y a partir de alli, cuando se visita un nuevo vértice, explorar cada camino que salga de él. Hasta que no se haya finalizado de explorar uno de los caminos no se comienza con el siguiente. Un camino deja de explorarse cuando se llega a un vértice ya visitado.
Si existían vértices no alcanzables desde v el recorrido queda incompleto; entonces, se debe seleccionar algún vértice como nuevo vértice de partida, y repetir el proceso.
Pérez, G. M. C.-. (2022). DFS - Recorrido en profundidad | Recorridos sobre grafos. DFS - Recorrido en profundidad. https://163.10.22.82/OAS/recorrido_grafos/dfs__recorrido_en_profundidad.html.
Presentación para los recorridos en los grafos
Plantilla para practicar los recorridos en los grafos
RETO GRAFOS DFS- PAREJAS
Es la sigla en inglés que quiere decir primero búsqueda en profundidad. Este algoritmo funciona ubicándose en un vértice cualquiera del grafo y determina los vértices adyacentes a este y escoge uno que aún no haya sido visitado y a partir de ahí realizar un llamado recursivo al mismo algoritmo.