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