Búsqueda en Profundidad

Búsqueda en Profundidad (DFS) es un algoritmo utilizado para recorrer o buscar a través de estructuras de grafo o árbol, explorando tan profundamente como sea posible en una rama antes de retroceder. En la recolección de datos web, DFS puede ser utilizado para explorar sitios web que tienen jerarquías de enlaces profundos, como foros o blogs, donde el objetivo es alcanzar los nodos más profundos posibles primero.

También conocido como: Búsqueda de recorrido profundo, búsqueda de retroceso.

Comparaciones

• DFS vs. BFS: DFS explora un camino completamente antes de pasar a otro, mientras que BFS (Búsqueda en Amplitud) explora todos los nodos al mismo nivel antes de profundizar.

• DFS vs. Algoritmo de Dijkstra: Mientras que DFS explora en profundidad primero, el Algoritmo de Dijkstra busca el camino más corto utilizando una cola de prioridad.

Pros

• Bajo uso de memoria: DFS requiere menos memoria que BFS, ya que solo necesita hacer un seguimiento del camino actual en lugar de todos los nodos en la profundidad actual.

• Eficiente para exploración profunda: Ideal para cosechar sitios web con enlaces profundamente anidados o explorar estructuras de árbol complejas.

• Implementación simple: Más fácil de implementar con recursión, lo que lo convierte en una opción directa para ciertas aplicaciones.

Contras

• Riesgo de quedarse atrapado en caminos profundos: DFS puede quedar atrapado en ramas profundas, especialmente en bucles infinitos, sin un manejo adecuado.

• Ineficiente para grafos amplios: Tarda más en explorar todos los nodos en grafos con grandes factores de ramificación en comparación con BFS.

• Puede no encontrar los caminos más cortos: DFS no garantiza el camino más corto, ya que prioriza la profundidad sobre la amplitud.

Ejemplo

Un raspador web utiliza DFS para explorar un sitio de blog, sumergiéndose profundamente en categorías o archivos anidados antes de retroceder para explorar otras secciones.