Algoritmo DFS 

Antes de empezar con la implementación te explicamos a grandes rasgos que es el algoritmo DFS:

DFS

El algoritmo DFS (Depth-First Search o Búsqueda en Profundidad) es un algoritmo para recorrer o buscar en un grafo. Comienza en un nodo raíz y explora tan lejos como sea posible a lo largo de cada rama antes de retroceder. Es un algoritmo de búsqueda no informada, lo que significa que no usa información heurística para guiar su búsqueda.

La idea principal detrás del DFS es explorar tanto como sea posible a lo largo de un camino antes de retroceder y explorar otros caminos. Utiliza una pila (ya sea implícita a través de la recursión o explícita) para realizar un seguimiento de los nodos que aún no se han visitado y los nodos que deben explorarse.

Aplicaciones del DFS

• Recorrido de Grafos: Visitando cada nodo del grafo exactamente una vez.
• Detección de Ciclos: Verificar si un grafo contiene ciclos.
• Componentes Conectados: Encontrar todos los nodos accesibles desde un nodo raíz dado.
• Ordenamiento Topológico: Ordenar los nodos de un grafo dirigido de manera que para cada arista dirigida de u a v, u aparece antes que v en el ordenamiento.
  Búsqueda de Caminos: Encontrar un camino entre dos nodos dados en un grafo.
  

Si deseas profundizar mas en el tema puedes ingresar a nuestro blog donde detallamos de mejor manera este tema  https://asimov.cloud/blog/programacion-5/algoritmos-dfs-y-bfs-en-un-grafo-199 

Implementación en  Python. 

Imagina que deseas recorrer por DFS el siguiente grafo.

El procedimiento seria el siguiente: 

La codificación en Python seria la siguiente: 

Si quiere aprender a detalle como programar un grafo en Python le recomendamos nuestro blog:  https://asimov.cloud/blog/programacion-5/programar-un-grafo-en-python-263#scrollTop=0 ,  donde explicamos como implementar un grafo en Python 

class Graph:

    def __init__(self):
        # Constructor de la clase Graph. Inicializa un diccionario para representar el grafo.
        self.graph = {}

    def add_vertex(self, vertex):
        # Método para agregar un vértice al grafo.
        if vertex not in self.graph:
            # Si el vértice no está en el grafo, lo agrega con un diccionario vacío para representar sus conexiones.
            self.graph[vertex] = {}


    def add_edge(self, vertex1, vertex2, weight=None, directed=False):
        # Método para agregar una arista al grafo entre dos vértices dados.
        self.add_vertex(vertex1)  # Aseguramos que los vértices estén presentes en el grafo.
        self.add_vertex(vertex2)
        self.graph[vertex1][vertex2] = weight  # Añade una conexión desde vertex1 a vertex2 con el peso dado.

        if not directed:
            # Si el grafo no es dirigido, añade también una conexión desde vertex2 a vertex1 con el mismo peso.
            self.graph[vertex2][vertex1] = weight



    def display(self):
        # Método para mostrar el grafo en forma legible.
        for vertex, edges in self.graph.items():

            print(f"Vértice {vertex} tiene como conexiones a:")
            for neighbor, weight in edges.items():

                if weight:
                    # Si hay peso en la conexión, imprime el vecino y su peso.
                    print(f"  - {neighbor} (peso: {weight})")
                else:
                    # Si no hay peso, imprime solo el vecino.
                    print(f"  - {neighbor}")



    def dfs_traversal(self, start_vertex, visited=None):

        # Método para realizar un recorrido en profundidad (Depth-First Search) desde un vértice dado.
        if visited is None:
            # Si no se proporciona un conjunto de vértices visitados, lo inicializamos como un conjunto vacío.
            visited = set()

        visited.add(start_vertex)  # Agregamos el vértice actual a los visitados.
        print(start_vertex, end=" ")  # Imprimimos el vértice actual.
        
        neighbors = self.graph[start_vertex]  # Obtenemos los vecinos del vértice actual.
        sorted_neighbors = sorted(neighbors, key=lambda x: neighbors[x])
        # Ordenamos los vecinos por orden ascendente de acuerdo al peso de la arista que los conecta.



        for neighbor in sorted_neighbors:
            # Recorremos los vecinos ordenados.
            if neighbor not in visited:
                # Si el vecino no ha sido visitado aún, realizamos una llamada recursiva para visitarlo.
                self.dfs_traversal(neighbor, visited)



# Ejemplo de uso:

g = Graph()
g.add_edge('A', 'B', weight=1)
g.add_edge('A', 'C', weight=1)
g.add_edge('B', 'D', weight=1)
g.add_edge('B', 'E', weight=1)
g.add_edge('C', 'F', weight=1)
g.add_edge('E', 'G', weight=1)
g.add_edge('F', 'H', weight=1)

print("Recorrido DFS:")
g.dfs_traversal('A')

Resultado: 

Al ejecutar el programa el resultado obtenido es el siguiente: 

             Recorrido DFS:           
              A B D E G C F H