Python en Español

Algoritmo Depth First Search en Python (múltiples ejemplos)

Depth First Search es un algoritmo gráfico transversal muy popular. En este tutorial, comprenderemos cómo funciona, junto con ejemplos; y cómo podemos implementarlo en Python.
Vamos a ver las siguientes secciones:

 

 

Introducción

Los Gráficos y los Árboles son una de las estructuras de datos más importantes que utilizamos para varias aplicaciones en la Ciencia de la Computación.

Representan datos en forma de nodos, que están conectados a otros nodos a través de “bordes”.

Al igual que otras estructuras de datos, recorrer todos los elementos o buscar un elemento en un gráfico o en un árbol es una de las operaciones fundamentales que se requiere para definir tales estructuras de datos. La Depth First Search es uno de esos algoritmos gráficos transversales.

El algoritmo de Depth First Search

Depth First Search comienza mirando el nodo raíz (un nodo arbitrario) de un gráfico. Si realizamos un recorrido por todo el gráfico, éste visita el primer hijo de un nodo de la raíz, luego, a su vez, mira el primer hijo de este nodo y continúa a lo largo de esta rama hasta llegar a un nodo de la hoja.

A continuación, retrocede y explora los otros hijos del nodo padre de manera similar. Esto continúa hasta que visitamos todos los nodos del árbol, y no queda ningún nodo padre para explorar.

Animación de El algoritmo de Depth First Search

Fuente: Wikipedia

Sin embargo, si estamos realizando una búsqueda de un elemento en particular, entonces en cada paso, se producirá una operación de comparación con el nodo en el que nos encontramos actualmente.

Si el elemento no está presente en un nodo en particular, entonces se realiza el mismo proceso de exploración de cada rama y retroceso.

Esto continúa hasta que o bien se han visitado todos los nodos del gráfico, o bien hemos encontrado el elemento que buscábamos.

 

Representar un grafico

Antes de intentar implementar el algoritmo DFS en Python, es necesario entender primero cómo representar un gráfico en Python.

Hay varias versiones de un gráfico. Un gráfico puede tener bordes dirigidos (definiendo la fuente y el destino) entre dos nodos, o bordes no dirigidos. Los bordes entre nodos pueden o no tener pesos. Dependiendo de la aplicación, podemos utilizar cualquiera de las diversas versiones de un gráfico.

A efectos de recorrer todo el gráfico, utilizaremos gráficos con bordes dirigidos (ya que necesitamos modelar la relación padre-hijo entre nodos), y los bordes no tendrán pesos ya que lo único que nos interesa es recorrer todo el gráfico.

Ahora bien, hay varias maneras de representar un gráfico en Python; dos de las más comunes son las siguientes:

  1. Matriz de Adyacencia
  2. Lista de Adyacencia

 

Matriz de Adyacencia

La Matriz de Adyacencia es una matriz cuadrada de forma N x N (donde N es el número de nodos en el gráfico).

Cada fila representa un nodo, y cada una de las columnas representa un hijo potencial de ese nodo.

Cada par (fila, columna) representa un borde potencial.

La existencia o no del borde depende del valor de la posición correspondiente en la matriz.

Un valor distinto de cero en la posición (i,j) indica la existencia de un borde entre los nodos i y j, mientras que el valor cero significa que no existe ningún borde entre i y j.

Los valores de la matriz de adyacencia pueden ser un número binario o un número real.

Podemos utilizar valores binarios en un gráfico no ponderado (1 significa que existe un borde, y un 0 significa que no existe).

En el caso de los valores reales, podemos utilizarlos para un gráfico ponderado y representar el peso asociado al borde entre la fila y la columna que representa la posición.

Por ejemplo, un valor 10 entre en la posición (2,3) indica que existe un borde con peso 10 entre los nodos 2 y 3.

En Python, podemos representar las matrices de adyacencia utilizando un NumPy array. De dos dimensiones.

 

Lista de adyacencia

La Lista de Adyacencia es una colección de varias listas. Cada lista representa un nodo en el gráfico, y almacena todos los vecinos/hijos de este nodo.
En Python, una lista de adyacencia puede ser representada usando un diccionario donde las claves son los nodos del gráfico, y sus valores son una lista que almacena los vecinos de estos nodos.
Usaremos esta representación para nuestra implementación del algoritmo DFS.
Tomemos un ejemplo de gráfico y lo representemos usando un diccionario en Python.

un gráfico de ejemplo para demostrar la representación del diccionario

El grafico dado tiene los siguientes cuatro bordes:

  1. A -> B
  2. A -> C
  3. B -> C
  4. C -> D

Vamos a crear un diccionario en Python para representar este gráfico.

graph = {"A": ["B", "C"],
            "B": ["C"],
            "C": ["D"]}

Ahora que sabemos como representar un grafico en Python, podemos pasar a la implementacion del algoritmo DFS.

Implementacióon del Depth First Search(un enfoque no recursivo)

Cnosideremos el grafico de ejemplo, mostrado en la animacion de la primera sección.

El gráfico de ejemplo utilizado para implementar DFS

Vamos a definir este gráfico como una lista de adyacencia utilizando el diccionario Python.

graph = {"A":["D","C","B"],
   "B":["E"],
   "C":["G","F"],
   "D":["H"],
   "E":["I"],
   "F":["J"]}

Uno de los órdenes de travesía esperados para este gráfico usando DFS sería:

Orden de recorrido DFS para el gráfico de ejemplo

Vamos a implementar un método que acepte un gráfico y lo atraviese usando DFS. Podemos lograrlo usando tanto la técnica de recursividad como el enfoque no recursivo e iterativo.

En esta sección, veremos el método iterativo.

Utilizaremos una pila y una lista para hacer un seguimiento de los nodos visitados.

Empezaremos por el nodo raíz, lo añadiremos a la ruta y lo marcaremos como visitado. Luego añadiremos todos sus vecinos a la pila.

En cada paso, sacaremos un elemento de la pila y comprobaremos si ha sido visitado.

Si no ha sido visitado, lo añadiremos al camino y añadiremos todos sus vecinos a la pila.

def dfs_non_recursive(graph, source):

       if source is None or source not in graph:

           return "Invalid input"

       path = []

       stack = [source]

       while(len(stack) != 0):

           s = stack.pop()

           if s not in path:

               path.append(s)

           if s not in graph:

               #leaf node
               continue

           for neighbor in graph[s]:

               stack.append(neighbor)

       return " ".join(path)

Nuestro método definido por el usuario toma el diccionario que representa el gráfico y un nodo fuente como entrada.

Tenga en cuenta que el nodo fuente tiene que ser uno de los nodos del diccionario, de lo contrario el método devolverá un error de “Entrada inválida”.

Llamemos a este método en nuestro gráfico definido, y verifiquemos que el orden de la travesía coincide con el demostrado en la figura anterior.

DFS_path = dfs_non_recursive(graph, "A")

print(DFS_path)

Salida :

salida de la implementación no recursiva de DFS en el gráfico

Por lo tanto, el orden de la travesía del gráfico está en la forma de “La profundidad primero”.

 

DFS utilizando un metodo recursivo

podemos implementar el algoritmo Depth First Search utilizando un enfoque popular de resolución de problemas llamado recursión.

La recursiones una tecnica en a cual el mismo problema es dividido en pequeñas instancias, y el mismo método es llamado recursivamente dentro de su cuerpo.

Definiremos un caso base dentro de nuestro método, que es – “Si el nodo de la hoja ha sido visitado, tenemos que retroceder”.

Vamos a implementar este método:

def recursive_dfs(graph, source,path = []):

       if source not in path:

           path.append(source)

           if source not in graph:
               # leaf node, backtrack
               return path

           for neighbour in graph[source]:

               path = recursive_dfs(graph, neighbour, path)


       return path

Ahora podemos crear nuestro gráfico (igual que en la sección anterior), y llamar al método recursivo.

graph = {"A":["B","C", "D"],
           "B":["E"],
           "C":["F","G"],
           "D":["H"],
           "E":["I"],
           "F":["J"]}


path = recursive_dfs(graph, "A")

print(" ".join(path))

Salida:

Salida de la implementación recursiva de DFS en el gráfico

El orden de la travesía es nuevamente de la forma “La Profundidad Primero”.

 

Depth First Search en un Arbol Bunario

¿Qué es un árbol binario?

Un árbol binario es un tipo especial de gráfico en el que cada nodo puede tener sólo dos hijos o ningún hijo.
Otra propiedad importante de un árbol binario es que el valor del hijo izquierdo del nodo será menor o igual que el valor del nodo actual.
Del mismo modo, el valor del hijo derecho es mayor que el valor del nodo actual.

Depth First Search en un Arbol Bunario

Así, cada valor de la rama izquierda del nodo de la raíz es más pequeño que el valor de la raíz, y los de la rama derecha tendrán un valor mayor que el de la raíz.
Entendamos cómo podemos representar un árbol binario usando clases de Python.

 

Representar Arboles Binarios utilizando Clases de Python

Podemos crear una clase que represente a cada nodo de un árbol, junto con sus hijos izquierdo y derecho.
Usando el objeto nodo raíz, podemos analizar todo el árbol.
También definiremos un método para insertar nuevos valores en un árbol binario.

class Node:

       def __init__(self, value):

           self.value = value

           self.left = None

           self.right = None


       def insert(self, value):

           if value:

               if value < self.value:

                   if self.left is None:

                       self.left = Node(value)

                   else:

                       self.left.insert(value)

               elif value > self.value:

                   if self.right is None:

                       self.right = Node(value)

                   else:

                       self.right.insert(value)

               else:

                   self.value = value

Vamos a crear ahora un objeto nodo raíz e insertar valores en él para construir un árbol binario como el que se muestra en la figura de la sección anterior.

root = Node(7)

root.insert(2)

root.insert(25)

root.insert(9)

root.insert(80)

root.insert(0)

root.insert(5)

root.insert(15)

root.insert(8)

Esto construirá el árbol binario que se muestra en la figura de arriba.
También asegurará que las propiedades de los árboles binarios, es decir, “2 niños por nodo” y “izquierda < raíz < derecha” se satisfagan sin importar en qué orden insertamos los valores.

 

Implementar DFS para un árbol binario

Definamos ahora una función recursiva que toma como entrada el nodo raíz y muestra todos los valores del árbol en el orden “Depth First Search”.

def dfs_binary_tree(root):

       if root is None:

           return

       else:

           print(root.value,end=" ")

           dfs_binary_tree(root.left)

           dfs_binary_tree(root.right)

Ahora podemos llamar a este método y pasar el objeto del nodo raíz que acabamos de crear.

dfs_binary_tree(root)

Salida:

salida de la implementación de DFS en el árbol binario

Este orden también se llama el “preorden transversal” de un árbol binario.

 

Depth First Search utilizando networkx

Hasta ahora, hemos estado escribiendo nuestra lógica para representar gráficos y atravesarlos.
Pero, como todas las demás aplicaciones importantes, Python ofrece una biblioteca para manejar los gráficos también. Se llama ‘networkx’.

‘networkx’ es un paquete de Python para representar gráficos usando nodos y bordes, y ofrece una variedad de métodos para realizar diferentes operaciones en los gráficos, incluyendo la travesía DFS.

Veamos primero cómo construir un gráfico usando networkx.

 

Construir un gráafico en networkx

Para construir un gráfico en networkx, primero creamos un objeto gráfico y luego añadimos todos los nodos del gráfico usando el método ‘add_node()’, seguido de la definición de todos los bordes entre los nodos, usando el método ‘add_edge()’.

Construyamos el siguiente gráfico usando ‘networkx

‘.

un gráfico de ejemplo para ser construido usando DFS

import networkx as nx

G = nx.Graph() #create a graph

G.add_node(1) # add single node

G.add_node(2)

G.add_node(3)

G.add_node(4)

G.add_node(5)

G.add_nodes_from([6,7,8,9]) #add multiple nodes

Ahora que hemos agregados todos los nodos, vamos a definir los ejes entre los nodos como se muestra en la figura.

# adding edges

G.add_edge(5,8)

G.add_edge(5,4)

G.add_edge(5,7)

G.add_edge(8,2)

G.add_edge(4,3)

G.add_edge(4,1)

G.add_edge(7,6)

G.add_edge(6,9)

 

Visualizar el grafico en DFS

Ahora, construimos el gráfico definiendo los nodos y bordes, veamos cómo se ve el método ‘draw()’ de la redx y verifiquemos si está construido de la manera que queríamos. Usaremos matplotlib para mostrar el gráfico.

import matplotlib.pyplot as plt

nx.draw(G, with_labels=True, font_weight='bold')

plt.show()

Salida:

visualización del gráfico usando networkx

La orientación puede ser un poco diferente a nuestro diseño, pero se parece al mismo gráfico, con los nodos y los mismos bordes entre ellos.

Ahora vamos a realizar el DFS transversal en este gráfico.

 

Gráfico tranversal en networkx – DFS

La ‘networkx’ ofrece una gama de métodos para atravesar el gráfico de diferentes maneras. Usaremos el método ‘dfs_preorder_nodes()’ para analizar el gráfico en el orden de búsqueda de profundidad primero.

El orden esperado de la figura debería ser:
5, 8, 2, 4, 3, 1, 7, 6, 9

Llamemos al método y veamos en qué orden imprime los nodos.

dfs_output = list(nx.dfs_preorder_nodes(G, source=5))

print(dfs_output)

Salida:

Gráfico tranversal en networkx

Por lo tanto, el orden de la travesía por la networkx está a lo largo de nuestras líneas esperadas.

Ahora que hemos entendido bien la búsqueda de profundidad o DFS traversal, veamos algunas de sus aplicaciones.

 

Clasificación Topológica utilizando Depth First Search

La clasificación topológica es una de las aplicaciones importantes de los gráficos utilizados para modelar muchos problemas de la vida real en los que el comienzo de una tarea depende de la finalización de alguna otra tarea.

Por ejemplo, podemos representar un número de trabajos o tareas usando los nodos de un gráfico.
Algunas de las tareas pueden depender de la finalización de alguna otra tarea. Esta dependencia se modela mediante bordes dirigidos entre nodos.
Un gráfico con bordes dirigidos se denomina gráfico dirigido.

Si queremos realizar una operación de programación a partir de un conjunto de tareas de este tipo, tenemos que asegurarnos de que no se viola la relación de dependencia, es decir, cualquier tarea que venga más tarde en una cadena de tareas se realiza siempre sólo después de todas las tareas antes de que haya terminado.
Podemos lograr este tipo de orden a través de la clasificación topológica del gráfico.

Nótese que para que la clasificación topológica sea posible, no tiene que haber ningún ciclo dirigido presente en el gráfico, es decir, el gráfico tiene que ser un  gráfico aciclico dirigido o DAG.

Tomemos un ejemplo de un DAG y hagamos una clasificación topológica en él, usando el enfoque de Depth First Search.

un ejemplo dirigido gráfico acíclico para la clasificación topológica

Digamos que cada nodo del gráfico anterior representa una tarea en una fábrica para producir un producto. Las flechas dirigidas entre el modelo de nodos son las dependencias de cada tarea en la realización de las tareas anteriores.

Por lo tanto, cualquiera que sea el orden de las tareas que elegimos realizar, para comenzar la tarea C, las tareas A y E deben haber sido completadas.

Del mismo modo, para realizar la tarea I, las tareas A, E, C y F deben haber sido completadas. Como no hay una flecha hacia adentro en el nodo H, la tarea H puede ser realizada en cualquier punto sin depender de la finalización de cualquier otra tarea.

Podemos construir tal gráfico dirigido usando el módulo ‘digraph’ de Python networkx.

dag = nx.digraph.DiGraph()

dag.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])

dag.add_edges_from([('A', 'B'), ('A', 'E'), ('B', 'D'), ('E', 'C'),
                      ('D', 'G'),('C', 'G'),('C', 'I'), ('F', 'I')])

Obsérvese que hemos utilizado los métodos ‘add_nodes_from()’ y ‘add_edges_from()’ para añadir todos los nodos y bordes de la gráfica dirigida a la vez.

Ahora podemos escribir una función para realizar la ordenación topológica utilizando DFS.

Empezaremos en un nodo sin flecha hacia adentro, y seguiremos explorando una de sus ramas hasta que lleguemos a un nodo de hoja, y luego retrocederemos y exploraremos otras ramas.

Una vez que exploremos todas las ramas de un nodo, marcaremos el nodo como “visitado” y lo empujaremos a una pila.

Una vez que cada nodo es visitado, podemos realizar repetidas operaciones de pop en la pila para darnos un orden topológico de las tareas.

Ahora vamos a traducir esta idea en una función de Python:

def dfs(dag, start, visited, stack):

       if start in visited:

           # node and all its branches have been visited
           return stack, visited


       if dag.out_degree(start) == 0:

           # if leaf node, push and backtrack
           stack.append(start)

           visited.append(start)

           return stack, visited

       #traverse all the branches
       for node in dag.neighbors(start):

           if node in visited:

               continue

           stack, visited = dfs(dag, node, visited, stack)

       #now, push the node if not already visited
       if start not in visited:

           print("pushing %s"%start)

           stack.append(start)

           visited.append(start)

       return stack, visited

   def topological_sort_using_dfs(dag):

       visited = []

       stack=[]

       start_nodes = [i for i in dag.nodes if dag.in_degree(i)==0]

   #     print(start_nodes)

       for s in start_nodes:

           stack, visited = dfs(dag, s, visited, stack)

       print("Topological sorted:")

       while(len(stack)!=0):

           print(stack.pop(), end=" ")

Hemos definido dos funciones: una para el recorrido recursivo de un nodo, y la función principal de clasificación topológica que primero encuentra todos los nodos sin dependencia y luego recorre cada uno de ellos utilizando el enfoque de Depth First Search.
Finalmente, saca valores de la pila, lo que produce una clasificación topológica de los nodos.

Llamemos ahora a la función ‘topological_sort_using_dfs()’

topological_sort_using_dfs(dag)

Salida:

salida de nuestra implementación de tipo topológico en el DAG

Si miramos de cerca el orden de salida, encontraremos que cada vez que cada uno de los trabajos comienza, tiene todas sus dependencias completadas antes de él.

También podemos comparar esto con la salida de un método de ordenación topológica incluido en el módulo ‘networkx’ llamado ‘topological_sort()’.

topological_sorting = nx.topological_sort(dag)

for n in topological_sorting:

    print(n, end=' ')

Salida:

salida de tipo topológico usando networkx

Parece que el ordenamiento producido por el método de clasificación de Networkx es el mismo que el producido por nuestro método.

 

Encontrar los componentes conectados usando DFS

Un gráfico tiene otra propiedad importante llamada los componentes conectados. Un componente conectado en un gráfico no dirigido se refiere a un conjunto de nodos en los que cada vértice está conectado a todos los demás vértices a través de un camino.

Veamos el siguiente ejemplo:

Encontrar los componentes conectados usando DFS

En el gráfico que se muestra arriba, hay tres componentes conectados; cada uno de ellos ha sido marcado en rosa.

Construyamos este gráfico en Python, y luego trazaremos una forma de encontrar los componentes conectados en él.

graph = nx.Graph()

graph.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])

graph.add_edges_from([('A', 'B'), ('B', 'E'), ('A', 'E')]) #component 1

graph.add_edges_from([('C', 'D'), ('D', 'H'), ('H', 'F'), ('F', 'C')]) #component 2

graph.add_edge('G','I') #component 3

Let’s also visualize it while we are at it.

import matplotlib.pyplot as plt

nx.draw(graph, with_labels=True, font_weight='bold')

plt.show()

Salida:

visualización del gráfico con componentes conectados usando networkx

ara encontrar los componentes conectados usando DFS, mantendremos un conjunto global común llamado “visitado”, y cada vez que encontremos una nueva variable que no haya sido visitada, empezaremos a encontrar de qué componente conectado forma parte.

Marcaremos cada nodo de ese componente como “visitado”, de modo que no podremos volver a visitarlo para encontrar otro componente conectado.

Repetiremos este procedimiento para cada nodo, y el número de veces que llamamos al método DFS para encontrar componentes conectados de un nodo, será igual al número de componentes conectados en el gráfico.

Escribamos esta lógica en Python y ejecutémosla en el gráfico que acabamos de construir:

def find_connected_components(graph):

       visited = []

       connected_components = []

       for node in graph.nodes:

           if node not in visited:

               cc = [] #connected component

               visited, cc = dfs_traversal(graph, node, visited, cc)

               connected_components.append(cc)

       return connected_components

   def dfs_traversal(graph, start, visited, path):

       if start in visited:

           return visited, path

       visited.append(start)

       path.append(start)

       for node in graph.neighbors(start):

           visited, path = dfs_traversal(graph, node, visited, path)

       return visited, path

Vamos a utilizar nuestro méetodo en el gráfico construido en el paso previo..

connected_components = find_connected_components(graph)

print("Total number of connected components =", len(connected_components))

for cc in connected_components:

    print(cc)

Salida:

salida de nuestra implementación de encontrar componentes conectados

 

Conclusión

En este blog, entendimos el algoritmo DFS y lo usamos de diferentes maneras.

Empezamos por entender cómo se puede representar un gráfico usando estructuras de datos comunes e implementamos cada una de ellas en Python.

Luego implementamos el algoritmo transversal de De usando tanto el enfoque recursivo como el no recursivo.

A continuación, miramos una forma especial de un gráfico llamado el árbol binario e implementamos el algoritmo DFS en el mismo.
Aquí representamos el árbol entero usando objetos nodales construidos a partir de la clase Python que definimos para representar un nodo.

Luego miramos la oferta de Python para representar gráficos y realizar operaciones en ellos – el módulo ‘networkx’.
Lo usamos para construir un gráfico, visualizarlo y ejecutar nuestro método DFS en él. Comparamos la salida con el propio método transversal de DFS del módulo.

Por último, nos fijamos en dos aplicaciones importantes de la Depth First Search, a saber, la clasificación topológica y la búsqueda de componentes conectados en un gráfico.

Mokhtar Ebrahim
Fundadora de LikeGeeks. Estoy trabajando como administrador de sistemas Linux desde 2010. Soy responsable de mantener, proteger y solucionar problemas de servidores Linux para múltiples clientes de todo el mundo. Me encanta escribir guiones de shell y Python para automatizar mi trabajo.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *