Algoritmos de búsqueda en profundidad (DFS)

7.1 Principios de funcionamiento del algoritmo DFS

Búsqueda en profundidad (Depth-First Search, DFS) — es un algoritmo de recorrido o búsqueda en un grafo. Comienza desde un vértice inicial y se adentra en el grafo hasta alcanzar un vértice sin vecinos no visitados, luego retrocede y continúa el proceso con otros vértices.

Pasos del algoritmo:

1. Comenzamos desde el vértice inicial elegido y lo marcamos como visitado.
2. Exploramos el primer vecino no visitado.
3. Repetimos los pasos 1 y 2 para este vecino.
4. Si todos los vecinos del vértice actual están visitados, retrocedemos al vértice anterior y continuamos el proceso.
5. El proceso se repite hasta que todos los vértices alcanzables desde el vértice inicial estén visitados.

Visualización:

Complejidad temporal y espacial del DFS:

Complejidad temporal:

O(V + E), donde V — es el número de vértices, E — es el número de aristas.

Cada nodo y cada arista del grafo se visitan una vez.

Complejidad espacial:

O(V), ya que se utiliza una pila de llamadas o una pila explícita para almacenar los vértices, así como arrays para almacenar el estado (vértices visitados).

7.2 Implementación de DFS utilizando recursión

Vamos a empezar implementando DFS usando recursión — el código será elegante y compacto.

Implementación recursiva de DFS:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Procesamiento del nodo
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# Ejemplo de uso:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Implementación de DFS utilizando una pila

Sin recursión, el código será un poco más largo, ya que necesitamos almacenar una lista de vértices visitados adicionalmente.

Implementación iterativa de DFS (utilizando una pila):

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Procesamiento del nodo
        
            for neighbor in reversed(graph[vertex]):  # Orden inverso para el orden correcto del recorrido
                if neighbor not in visited:
                    stack.append(neighbor)
        
# Ejemplo de uso:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 Ejemplos de problemas resueltos usando DFS

Ejemplos clásicos de problemas resueltos usando DFS:

1. Búsqueda de caminos en un laberinto:

Se utiliza para encontrar un camino en un laberinto desde el punto de inicio hasta el final.

Aplicación:

En videojuegos y robótica para navegar laberintos y espacios complejos.

2. Comprobación de conexidad de un grafo:

Verificar si un grafo es conexo (si hay un camino entre cualquier par de vértices).

Aplicación:

En análisis de redes para verificar la conexidad de una red.

3. Ordenamiento topológico:

Se utiliza para ordenar los vértices de un grafo dirigido acíclico (DAG) de manera que para cualquier arista (u, v) el vértice u precede al vértice v.

Aplicación:

En compiladores para ordenar dependencias y tareas.

4. Detección de ciclos en un grafo:

Verificar si un grafo contiene ciclos.

Aplicación:

En análisis de dependencias para detectar dependencias cíclicas.

5. Generación de laberintos:

Uso de DFS para generar laberintos aleatorios.

Aplicación:

En aplicaciones de juegos y entretenimiento para crear laberintos.