Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Una implementación estándar de DFS coloca cada vértice del gráfico en una de las dos categorías, visitado o no visitado. El objetivo del algoritmo es marcar cada vértice como visitado evitando los ciclos. En este algoritmo:

1. Se inicia colocando uno de los vértices del grafo en la parte superior de una pila.
2. Se toma el elemento superior de la pila y se añade a la lista de vértices visitados.
3. Se crea una lista de los nodos adyacentes a ese vértice.
4. Se añade los que no están en la lista de visitados a la parte superior de la pila.
5. Se repite los pasos 2 y 3 hasta que la pila esté vacía.

Solución recursiva:

1. Crear una función recursiva que tome el índice del nodo y un array visitado.
2. Marque el nodo actual como visitado e imprima el nodo.
3. Recorrer todos los nodos adyacentes y no marcados y llamar a la función recursiva con el índice del nodo adyacente.

Solución iterativa:

Primero se insertan todos los elementos en la pila y luego se hace uso de la cabeza de la pila (que es el último nodo insertado), así que el primer nodo que se maneja es el último hijo.

def dfs(raiz):
   pila = []
   visitados = set()
   pila.append(raiz)
 
   while pila: #comprueba si hay algo en la lista de tareas pendientes
       nodoActual = pila.pop() # accede al nodo siguiente
       if nodoActual not in visitados: # actualiza los nodos visitados si este nodo no habia sido visitado antes
           visitados.add(nodoActual)
       for nodo in nodoActual.nodosAdyacentes: # itera sobre los nodos adyacentes
           if nodo not in visitados:
               pila.append(nodo) # añade a la lista de tareas pendientes