Gráficos en Python - Teoría e implementación - Algoritmo de búsqueda en profundidad (DFS)

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de modo...

En esta lección, veremos uno de los dos algoritmos complementarios, fundamentales y más simples para el recorrido de gráficos: Búsqueda primero en profundidad (DFS). Es el algoritmo más utilizado junto con la Búsqueda en amplitud (BFS) relacionada dada su simplicidad. Después de repasar la idea principal utilizada para DFS, la implementaremos en Python en una representación gráfica: una lista de adyacencia.

Búsqueda primero en profundidad - Teoría {# depthfirstsearchtheory}

La búsqueda en profundidad (DFS) es un algoritmo utilizado para atravesar o ubicar un nodo objetivo en una estructura de datos de gráfico o árbol. Da prioridad a la profundidad y busca a lo largo de una rama, hasta donde puede llegar, hasta el final de esa rama. Una vez allí, retrocede hasta la primera divergencia posible de esa rama y busca hasta el final de esa rama, repitiendo el proceso.

Dada la naturaleza del algoritmo, puede implementarlo fácilmente de forma recursiva, y siempre puede implementar un algoritmo recursivo también de forma iterativa:

animación dfs

El nodo de inicio es el nodo raíz para las estructuras de datos de árbol, mientras que con gráficos más genéricos, puede ser cualquier nodo.

DFS se usa ampliamente como parte de muchos otros algoritmos que resuelven problemas representados por gráficos. Desde búsquedas de ciclos, búsqueda de caminos, clasificación topológica, hasta encontrar puntos de articulación y componentes fuertemente conectados. La razón detrás de este uso generalizado del algoritmo DFS radica en su simplicidad general y su fácil implementación recursiva.

El algoritmo DFS

El algoritmo DFS es bastante simple y consta de los siguientes pasos:

  1. Marque el nodo actual como visitado.
  2. Atraviese los nodos vecinos que no se visitan y llame recursivamente a la función DFS para ese nodo.

El algoritmo se detiene cuando se encuentra el nodo de destino o cuando se recorre todo el gráfico (se visitan todos los nodos).

{.icon aria-hidden=“true”}

Nota: Dado que los gráficos pueden tener ciclos, necesitaremos un sistema para evitarlos y no caer en bucles infinitos. Es por eso que "marcamos" cada nodo que pasamos como visitado al agregarlos a un Conjunto que contiene solo entradas únicas.

Al marcar los nodos como "visitados", si alguna vez volvemos a encontrar ese nodo, ¡estamos en un bucle! Se ha desperdiciado tiempo y potencia computacional interminables en bucles, perdidos en el éter.

Pseudocódigo

Dados estos pasos, podemos resumir DFS en pseudocódigo:

1
2
3
4
5
6
7
DFS(G, u):
    # Input processing
    u.visited = true
    for each v in G.adj[u]:
        if !v.visited:
            DFS(G, v)
            # Output processing

El procesamiento de entrada y salida se realiza según el propósito de la búsqueda del gráfico. Nuestro procesamiento de entrada para DFS verificará si el nodo actual es igual al nodo objetivo.

Con esta vista, realmente puede comenzar a apreciar cuán simple pero útil es este algoritmo.

Búsqueda primero en profundidad - Implementación {# depthfirstsearchimplementation}

Lo primero que debemos considerar antes de sumergirnos en la implementación del algoritmo DFS en sí mismo es cómo implementar un gráfico. Como en cualquier otro artículo de esta serie, hemos optado por implementarlo utilizando un Gráfico bastante básico. clase. Contiene una representación gráfica y un par de métodos que necesita para operar con gráficos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Graph:
    # Constructor
    def __init__(self, num_of_nodes, directed=True):
        self.m_num_of_nodes = num_of_nodes
        self.m_nodes = range(self.m_num_of_nodes)
        
        # Directed or Undirected
        self.m_directed = directed
        
        # Graph representation - Adjacency list
        # We use a dictionary to implement an adjacency list
        self.m_adj_list = {node: set() for node in self.m_nodes}      
    
    # Add edge to the graph
    def add_edge(self, node1, node2, weight=1):
        self.m_adj_list[node1].add((node2, weight))

        if not self.m_directed:
            self.m_adj_list[node2].add((node1, weight))
    
    # Print the graph representation
    def print_adj_list(self):
        for key in self.m_adj_list.keys():
            print("node", key, ": ", self.m_adj_list[key])

Recapitulemos rápidamente cómo funciona la clase Graph. El método __init__() define un constructor. Consiste en una cantidad de nodos, un conjunto de nodos y la representación gráfica. En este caso, un gráfico está representado por una lista de adyacencia, efectivamente un diccionario de Python con cada nodo del gráfico configurado como una clave. Se asigna un conjunto de nodos adyacentes a cada nodo (clave).

{.icon aria-hidden=“true”}

Nota: Una lista de adyacencia es un tipo de representación gráfica en el código, consta de claves que representan cada nodo y un conjunto de valores para cada uno de ellos que contiene nodos que están conectados a la clave nodo con una arista.
Usar un diccionario para esto es la forma más fácil de representar rápidamente un gráfico en Python, aunque también puede definir sus propias clases de “Nodo” y agregarlas a una instancia de “Gráfico”.

Como sugiere su nombre, el método add_edge() se usa para agregar bordes a la representación del gráfico. Cada borde se representa como en cualquier lista de adyacencia habitual. Por ejemplo, el borde ‘1-2’ se representa agregando ‘2’ como el nodo adyacente del nodo ‘1’ en la lista de adyacencia. Además, nuestra implementación le permite asignar un peso a cualquier borde.

Por último, hemos creado el método que imprime la representación gráfica: print_adj_list().

Ahora podemos implementar el algoritmo DFS en la clase Graph. La implementación de la búsqueda en profundidad primero suele ser recursiva en el código dado lo natural que es un par, pero también se puede implementar fácilmente de forma no recursiva. Usaremos el método recursivo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def dfs(self, start, target, path = [], visited = set()):
    path.append(start)
    visited.add(start)
    if start == target:
        return path
    for (neighbour, weight) in self.m_adj_list[start]:
        if neighbour not in visited:
            result = self.dfs(neighbour, target, path, visited)
            if result is not None:
                return result
    path.pop()
    return None    

Agregamos el nodo de inicio al comienzo de nuestra ruta transversal y lo marcamos como visitado al agregarlo a un conjunto de nodos visitados. Luego, atravesamos los vecinos del nodo de inicio que no ya han sido visitados y llamamos a la función recursivamente para cada uno de ellos. Las llamadas recursivas dan como resultado profundizar tanto como podamos a lo largo de una "rama".

Luego guardamos una referencia al resultado. En el caso de que la función devuelva Ninguno, eso significa que el nodo de destino no se encontró en esta rama y que debemos probar con otra. Si la llamada recursiva, de hecho, no devuelve Ninguno, eso significa que hemos encontrado nuestro nodo de destino y devolvemos la ruta transversal como resultado.

Al final, si nos encontramos fuera del bucle for, significa que todas las ramas vecinas del nodo actual han sido visitadas y ninguna de ellas conduce a nuestro nodo de destino. Entonces, eliminamos el nodo actual de la ruta y devolvemos Ninguno como resultado.

Ejecutando DFS

Ilustremos cómo funciona el código a través de un ejemplo. Como hemos dicho antes, usaremos la clase Graph para representar el gráfico. Internamente, representa un gráfico como una lista de adyacencia. Aquí está el gráfico que usaremos en el siguiente ejemplo:

gráfico

Buscaremos una ruta desde el nodo 0 hasta el nodo 3, si existe, la ruta se guardará en un conjunto de nodos visitados, llamado traversal_path para que podamos reconstruirla para imprimirla.

Lo primero que debemos hacer es crear una instancia de la clase Graph. Nuestro gráfico de ejemplo es no dirigido y tiene 5 nodos, por lo que crearemos su representación de la siguiente manera:

1
graph = Graph(5, directed=False)

Esto creará la instancia de Graph que representa un gráfico no dirigido con 5 nodos. A continuación, debemos agregar todos los bordes del gráfico de ejemplo a nuestra representación gráfica:

1
2
3
4
5
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

Ahora, hemos creado la representación completa del gráfico de ejemplo. Echemos un vistazo a cómo la clase Graph almacena internamente nuestro gráfico de ejemplo:

1
graph.print_adj_list()

Lo que genera lo siguiente:

1
2
3
4
5
node 0 :  {(1, 1), (2, 1)}
node 1 :  {(0, 1), (3, 1)}
node 2 :  {(0, 1), (3, 1)}
node 3 :  {(1, 1), (4, 1), (2, 1)}
node 4 :  {(3, 1)}

Esto muestra la estructura del diccionario utilizado para representar una lista de adyacencia. Está perfectamente en línea con la implementación de una lista de adyacencia provista en la lección sobre representaciones gráficas en Python.

Finalmente, podemos encontrar una ruta desde el nodo 0 hasta el nodo 3:

1
2
3
traversal_path = []
traversal_path = graph.dfs(0, 3)
print(traversal_path)

Esto generará la ruta encontrada:

1
[0, 1, 3]

Ahora sería útil echar un vistazo a los pasos que tomó nuestro algoritmo:

  • Agregue el nodo 0 a la ruta transversal y márquelo como visitado. Compruebe si el nodo 0 es igual al nodo de destino 3, ya que no lo es, continúe y atraviese sus vecinos (1 y 2).
  • ¿Se visita al vecino 1? - No. Entonces, el algoritmo llama recursivamente a la función para ese nodo.
    • Recursive call for node 1: Add node 1 to the traversal path and mark it as visited. Is 1 equal to our target node 3? - No, continue and traverse its neighbors (0 and 3).
    • Is neighbor 0 visited? - Yes, move on to the next one.
    • Is neighbor 3 visited? - No, call the function recursively for this node.
      • Recursive call for node 3: Add node 3 to the traversal path and mark it as visited. Is 3 equal to our target node 3? - Yes, the target node has been found, return the traversal path.

Ruta de nodo actual visitada


0 [0] {0} 1 [0, 1] {0, 1} 3 [0, 1, 3] {0, 1, 3}

El algoritmo se detiene y nuestro programa imprime la ruta transversal resultante desde el nodo 0 hasta el nodo 3:

1
[0, 1, 3]

Después de la búsqueda, los nodos marcados en el gráfico representan el camino que tomamos para llegar al nodo de destino:

gráfico marcado

En caso de que no hubiera una ruta entre el nodo de inicio y el de destino, la ruta transversal estaría vacía.

{.icon aria-hidden=“true”}

Nota: Los gráficos también se pueden desconectar, lo que significa que hay al menos dos nodos que no se pueden conectar mediante una ruta. En este caso, DFS ignoraría los nodos a los que no puede acceder.

grafo desconectado

Por ejemplo, en este gráfico, si tuviéramos que iniciar DFS desde el nodo 0 hasta el nodo 4, no existiría tal ruta porque no tiene forma de llegar al nodo de destino.

Licensed under CC BY-NC-SA 4.0