Introducción

Los gráficos y árboles son una de las estructuras de datos más importantes que utilizamos para diversas aplicaciones en informática.
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, atravesar todos los elementos o buscar un elemento en un gráfico o un árbol es una de las operaciones fundamentales que se requieren para definir dichas estructuras de datos. Depth First Search es uno de esos algoritmos de recorrido de gráficos.

El algoritmo de búsqueda de profundidad primero

La búsqueda de profundidad primero comienza mirando el nodo raíz (un nodo arbitrario) de un gráfico. Si estamos realizando un recorrido de todo el gráfico, visita al primer hijo de un nodo raíz, luego, a su vez, mira al primer hijo de este nodo y continúa a lo largo de esta rama hasta que alcanza un nodo hoja.

A continuación, retrocede y explora a 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 principal por explorar.

fuente:  Wikipedia

Sin embargo, si estamos realizando una búsqueda de un elemento en particular, entonces, en cada paso, ocurrirá una operación de comparación con el nodo en el que nos encontramos.
Si el elemento no está presente en un nodo en particular, se lleva a cabo el mismo proceso de exploración de cada rama y retroceso.

Esto continúa hasta que se hayan visitado todos los nodos del gráfico o hayamos encontrado el elemento que estábamos buscando.

Representar un gráfico

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

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

Para el propósito de recorrer todo el gráfico, usaremos gráficos con bordes dirigidos (ya que necesitamos modelar la relación padre-hijo entre los nodos), y los bordes no tendrán pesos ya que todo lo que nos importa es el recorrido completo del gráfico. .

Ahora hay varias formas de representar un gráfico en Python; dos de las formas 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 una ventaja 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 un borde entre i y j.

Los valores de la matriz de adyacencia pueden ser un número binario o un número real.
Podemos usar valores binarios en un gráfico no ponderado (1 significa que existe borde y 0 significa que no).
Para valores reales, podemos usarlos para un gráfico ponderado y representar el peso asociado con el borde entre la fila y la columna que representan la posición.

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

En Python, podemos representar las matrices de adyacencia usando una matriz NumPy bidimensional .

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 se puede representar 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 gráfico de ejemplo y representémoslo usando un diccionario en Python.

El gráfico dado tiene los siguientes cuatro bordes:

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

Ahora creemos un diccionario en Python para representar este gráfico.

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

Ahora que sabemos cómo representar un gráfico en Python, podemos pasar a la implementación del algoritmo DFS.

Implementación de la búsqueda en profundidad (un enfoque no recursivo)

Consideraremos el ejemplo de gráfico que se muestra en la animación de la primera sección.

Definamos este gráfico como una lista de adyacencia usando el diccionario de Python.

1
2
3
4
5
6
graph = {"A":["D","C","B"],
   "B":["E"],
   "C":["G","F"],
   "D":["H"],
   "E":["I"],
   "F":["J"]}

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

Implementemos un método que acepte un gráfico y lo atraviese usando DFS. Podemos lograr esto utilizando tanto la técnica de recursividad como un enfoque iterativo no recursivo.
En esta sección, veremos el método iterativo.

Usaremos una pila y una lista para realizar un seguimiento de los nodos visitados.
Comenzaremos en el nodo raíz, lo agregaremos a la ruta y lo marcaremos como visitado. Luego agregaremos todos sus vecinos a la pila.
En cada paso, sacaremos un elemento de la pila y comprobaremos si se ha visitado.
Si no ha sido visitado, lo agregaremos a la ruta y agregaremos todos sus vecinos a la pila.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
17
18
19
20
21
22
23
24
25
26
27
28
def dfs_non_recursive(graph, source):
 
       if source is None or source not in graph:
 
           return "Invalid input"
 
       path = []
 
       stack =
 
       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 de origen tiene que ser uno de los nodos del diccionario; de lo contrario, el método devolverá un error de "Entrada no válida".

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

1
2
3
DFS_path = dfs_non_recursive(graph, "A")
 
print(DFS_path)

Salida  :

Por lo tanto, el orden de recorrido del gráfico es de la manera "Profundidad primero".

DFS usando un método recursivo

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

La recursividad es una técnica en la que el mismo problema se divide en instancias más pequeñas y el mismo método se llama recursivamente dentro de su cuerpo.

Definiremos un caso base dentro de nuestro método, que es - 'Si el nodo hoja ha sido visitado, necesitamos retroceder'.

Implementemos el método:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
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:
 
               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.

01
02
03
04
05
06
07
08
09
10
11
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:

El orden de recorrido es de nuevo en profundidad.

Primera búsqueda en profundidad en un árbol binario

¿Qué es un árbol binario?

Un árbol binario es un tipo especial de gráfico en el que cada nodo puede tener solo 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.
De manera similar, el valor del hijo derecho es mayor que el valor del nodo actual.

Por lo tanto, cada valor en la rama izquierda del nodo raíz es menor que el valor en 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 árboles binarios mediante clases de Python

Podemos crear una clase para representar cada nodo en un árbol, junto con sus hijos izquierdo y derecho.
Usando el objeto del nodo raíz, podemos analizar todo el árbol.

También definiremos un método para insertar nuevos valores en un árbol binario.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
17
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 anterior.
También asegurará que las propiedades de los árboles binarios, es decir, '2 hijos por nodo' e 'izquierda <raíz <derecha' se satisfagan sin importar en qué orden insertemos los valores.

Implementando DFS para un árbol binario

Definamos ahora una función recursiva que tome como entrada el nodo raíz y muestre todos los valores en el árbol en el orden de 'Profundidad primero búsqueda'.

01
02
03
04
05
06
07
08
09
10
11
12
13
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 de nodo raíz que acabamos de crear.

1
dfs_binary_tree(root)

Salida:

Este orden también se denomina 'recorrido de preorden' de un árbol binario.

Primera búsqueda en profundidad usando networkx

Hasta ahora, hemos estado escribiendo nuestra lógica para representar gráficos y recorrerlos.
Pero, como todas las demás aplicaciones importantes, Python también ofrece una biblioteca para manejar gráficos. 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 gráficos, incluido el recorrido DFS.

Primero veamos cómo construir un gráfico usando networkx.

Construyendo un gráfico en networkx

Para construir un gráfico en networkx, primero creamos un objeto gráfico y luego agregamos todos los nodos en el 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'.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
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 agregado todos los nodos, definamos los bordes entre estos nodos como se muestra en la figura.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
17
# 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)

Visualizando el gráfico en DFS

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

1
2
3
4
5
import matplotlib.pyplot as plt
 
nx.draw(G, with_labels=True, font_weight='bold')
 
plt.show()

Salida:

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.

Realicemos ahora un recorrido DFS en este gráfico.

Gráfico transversal en networkx - DFS

El 'networkx' ofrece una variedad de métodos para recorrer el gráfico de diferentes maneras. Usaremos el método 'dfs_preorder_nodes ()' para analizar el gráfico en el orden de búsqueda en profundidad.

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

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

1
2
3
dfs_output = list(nx.dfs_preorder_nodes(G, source=5))
 
print(dfs_output)

Salida:

Por lo tanto, el orden de recorrido por networkx sigue nuestras líneas esperadas.

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

Clasificación topológica mediante la búsqueda en profundidad primero

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

Por ejemplo, podemos representar una serie de trabajos o tareas utilizando nodos de un gráfico.
Algunas de las tareas pueden depender de la realización de alguna otra tarea. Esta dependencia se modela a través de  bordes dirigidos  entre nodos.
Una gráfica con bordes dirigidos se llama gráfica dirigida.

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 viole la relación de dependencia, es decir, cualquier tarea que venga más tarde en una cadena de tareas siempre se realiza solo después de todas las tareas antes de que haya terminado. .
Podemos lograr este tipo de orden mediante la clasificación topológica del gráfico.

Tenga en cuenta que para que sea posible la clasificación topológica, no debe haber un ciclo dirigido presente en el gráfico, es decir, el gráfico debe ser un  gráfico acíclico dirigido  o DAG.

Tomemos un ejemplo de un DAG y realicemos una clasificación topológica en él, utilizando el enfoque de búsqueda en profundidad.

Digamos que cada nodo en el 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 finalizació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 haberse completado.

Del mismo modo, para realizar la tarea I, las tareas A, E, C y F. deben haberse completado. Dado que no hay una flecha hacia adentro en el nodo H, la tarea H se puede realizar en cualquier punto sin depender de la finalización de ninguna otra tarea.

Podemos construir un gráfico dirigido usando el módulo 'digraph' de Python networkx.

1
2
3
4
5
6
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')])

Tenga en cuenta que hemos utilizado los métodos 'add_nodes_from ()' y 'add_edges_from ()' para agregar todos los nodos y bordes del gráfico dirigido a la vez.

Ahora podemos escribir una función para realizar una clasificación topológica usando DFS.

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

Una vez que exploramos todas las ramas de un nodo, marcaremos el nodo como 'visitado' y lo enviaremos a una pila.

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

Ahora traduzcamos esta idea en una función de Python:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
dieciséis
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53