ACTIVIDAD 8

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

Diapositivas de clase sobre recorridos de grafos

Archivo de Excel con el trabajo en clase y el taller en clase