Gráficos en Python - Teoría e implementación - Algoritmo Breadth-First Search (BFS)

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, repasaremos la teoría detrás del algoritmo y la implementación de Python de Breadth-First Search and Traversal. Primero, nos centraremos en la búsqueda de nodos, antes de profundizar en el recorrido de gráficos usando el algoritmo BFS, como las dos tareas principales para las que puede emplearlo.

{.icon aria-hidden=“true”}

Nota: Estamos asumiendo un gráfico implementado de lista de adyacencia en la lección.

Búsqueda primero en amplitud - Teoría

Búsqueda primero en amplitud (BFS) atraviesa el gráfico sistemáticamente, nivel por nivel, formando un árbol BFS a lo largo del camino.

Si comenzamos nuestra búsqueda desde el nodo v (el nodo raíz de nuestro gráfico o estructura de datos de árbol), el algoritmo BFS primero visitará todos los vecinos del nodo v (sus nodos secundarios, en nivel uno), en el orden que se da en la lista de adyacencia. A continuación, toma en consideración los nodos secundarios de esos vecinos (nivel dos), y así sucesivamente.

Este algoritmo se puede utilizar tanto para gráficos recorridos como para búsquedas. Al buscar un nodo que cumpla una determinada condición (nodo de destino), la ruta con la distancia más corta desde el nodo inicial hasta el nodo de destino. La distancia se define como el número de ramas recorridas.

BFS animated

Búsqueda primero en amplitud se puede utilizar para resolver muchos problemas, como encontrar el camino más corto entre dos nodos, determinar los niveles de cada nodo e incluso resolver juegos de rompecabezas y laberintos.

Si bien no es el algoritmo más eficiente para resolver grandes laberintos y acertijos, y es eclipsado por algoritmos como el Algoritmo de Dijkstra y A*, aún juega un papel importante en el grupo y dependiendo del problema en cuestión: DFS y BFS pueden superar a sus primos heurísticos.

Breadth-First Search - Algoritmo

Al implementar BFS, generalmente usamos una estructura FIFO como una Cola para almacenar los nodos que se visitarán a continuación.

{.icon aria-hidden=“true”}

Nota: Para usar una Cola en Python, necesitamos importar la clase Queue correspondiente del módulo queue.

Debemos prestar atención para no caer en bucles infinitos al volver a visitar los mismos nodos una y otra vez, lo que puede suceder fácilmente con gráficos que tienen ciclos. Teniendo eso en cuenta, realizaremos un seguimiento de los nodos que han sido visitados. Esa información no tiene que guardarse explícitamente, simplemente podemos realizar un seguimiento de los nodos principales, para que no volvamos accidentalmente a uno después de haberlo visitado.

Para resumir la lógica, los pasos del algoritmo BFS se ven así:

  1. Agregue el nodo raíz/de inicio a Queue.
  2. Para cada nodo, configure que no tengan un nodo principal definido.
  3. Hasta que la Cola esté vacía:
    • Extract the node from the beginning of the Queue.
    • Perform output processing.
    • For every neighbor of the current node that doesn't have a defined parent (is not visited), add it to the Queue, and set the current node as their parent.

{.icon aria-hidden=“true”}

El procesamiento de salida se realiza según el propósito detrás de la búsqueda de gráficos. Al buscar un nodo de destino, el procesamiento de salida suele probar si el nodo actual es igual al nodo de destino. ¡Este es el paso en el que puedes ser creativo!

Implementación de Breadth-First Search: búsqueda de nodo de destino

Comencemos primero con buscar y buscar un nodo de destino. Además del nodo de destino, también necesitaremos un nodo de inicio. El resultado esperado es una ruta que nos lleva desde el nodo de inicio hasta el nodo de destino.

Con eso en mente, y teniendo en cuenta los pasos del algoritmo, podemos implementarlo. Definiremos una clase Graph para "envolver" la implementación de la búsqueda BFS.

Graph contiene una representación gráfica, en este caso una matriz de adyacencia, y todos los métodos que pueda necesitar cuando trabaje con gráficos. Implementaremos tanto la búsqueda BFS como el recorrido BFS como métodos de esa clase:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from queue import Queue

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])

Después de implementar una clase envoltura, podemos implementar la búsqueda BFS como uno de sus métodos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def bfs(self, start_node, target_node):
    # Set of visited nodes to prevent loops
    visited = set()
    queue = Queue()

    # Add the start_node to the queue and visited list
    queue.put(start_node)
    visited.add(start_node)
    
    # start_node has not parents
    parent = dict()
    parent[start_node] = None

    # Perform step 3
    path_found = False
    while not queue.empty():
        current_node = queue.get()
        if current_node == target_node:
            path_found = True
            break

        for (next_node, weight) in self.m_adj_list[current_node]:
            if next_node not in visited:
                queue.put(next_node)
                parent[next_node] = current_node
                visited.add(next_node)
                
    # Path reconstruction
    path = []
    if path_found:
        path.append(target_node)
        while parent[target_node] is not None:
            path.append(parent[target_node]) 
            target_node = parent[target_node]
        path.reverse()
    return path 

Cuando estamos reconstruyendo la ruta (si se encuentra), vamos hacia atrás desde el nodo de destino, a través de sus padres, volviendo a rastrear todo el camino hasta el nodo de inicio. Además, invertimos el camino de nuestra propia intuición de ir desde start_node hacia target_node, aunque este paso es opcional.

Por otro lado, si no hay ruta, el algoritmo devolverá una lista vacía.

Con la implementación explicada anteriormente en mente, podemos probarla ejecutando la búsqueda BFS en el gráfico de ejemplo:

search graph

Vamos a recrear este gráfico usando nuestra clase Graph. Es un gráfico no dirigido con 6 nodos, así que lo instanciaremos como:

1
graph = Graph(6, directed=False)

A continuación, debemos agregar todos los bordes del gráfico a la instancia de la clase Graph que hemos creado:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(0, 3)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 5)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)

Ahora, veamos cómo la clase Graph representa internamente nuestro gráfico de ejemplo.

1
graph.print_adj_list()

Esto imprimirá la lista de adyacencia utilizada para representar un gráfico que hemos creado:

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

En este momento, hemos creado un gráfico y entendemos cómo se almacena como una matriz de adyacencia. Con todo eso en mente, podemos realizar una búsqueda en sí. Digamos que nos gustaría buscar nodo 5 a partir de nodo 0:

1
2
3
path = []
path = graph.bfs(0, 5)
print(path)

Ejecutar este código da como resultado:

1
[0, 3, 5]

Después de echar un vistazo rápido al gráfico de ejemplo, podemos ver que el camino más corto entre 0 y 5 es de hecho [0, 3, 5]. Sin embargo, también podría atravesar [0, 2, 5] y [0, 4, 5]. Estas rutas alternativas son, fundamentalmente, la misma distancia que [0, 3, 5]; sin embargo, considere cómo BFS compara los nodos. "Escanea" de izquierda a derecha y 3 es el primer nodo en el lado izquierdo de la lista de adyacencia que conduce a 5, por lo que se toma este camino en lugar de los demás.

Esta es una característica de BFS que querrá anticipar. Buscará de izquierda a derecha y no encontrará una ruta igualmente válida si se encuentra “después” de la primera.

{.icon aria-hidden=“true”}

Nota: Hay casos en los que no se puede encontrar una ruta entre dos nodos. Este escenario es típico para gráficos desconectados, donde hay al menos dos nodos que no están conectados por una ruta.

Así es como se ve un gráfico desconectado:

disconnected graph

Si intentáramos realizar una búsqueda de una ruta entre los nodos ‘0’ y ‘3’ en este gráfico, esa búsqueda no tendría éxito y se devolvería una ruta vacía.

Implementación Breadth-First - Gráfico transversal

Breadth-First Traversal es un caso especial de Breadth-First Search que atraviesa el gráfico completo, en lugar de buscar un nodo de destino. El algoritmo sigue siendo el mismo que hemos definido antes, con la diferencia de que no buscamos un nodo de destino y no necesitamos encontrar una ruta que conduzca a él.

Esto simplifica significativamente la implementación: imprimamos cada nodo que se atraviesa para obtener una intuición de cómo pasa a través de los nodos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def bfs_traversal(self, start_node):
    visited = set()
    queue = Queue()
    queue.put(start_node)
    visited.add(start_node)

    while not queue.empty():
        current_node = queue.get()
        print(current_node, end = " ")
        for (next_node, weight) in self.m_adj_list[current_node]:
            if next_node not in visited:
                queue.put(next_node)
                visited.add(next_node)  

{.icon aria-hidden=“true”}

Nota: Este método debe implementarse como parte de la clase Graph implementada anteriormente.

Ahora, definamos el siguiente gráfico de ejemplo de la manera mostrada anteriormente:

traversal graph

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Create an instance of the `Graph` class
# This graph is undirected and has 5 nodes
graph = Graph(5, directed=False)

# Add edges to the graph
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(1, 4)
graph.add_edge(2, 3)

Finalmente, ejecutemos el código:

1
graph.bfs_traversal(0)

Ejecutar este código imprimirá los nodos en el orden en que BFS los escaneó:

1
0 1 2 4 3

Paso a paso

Profundicemos un poco más en este ejemplo y veamos cómo funciona el algoritmo paso a paso. A medida que comenzamos el recorrido desde el nodo de inicio 0, se coloca en el conjunto visitado y también en la cola. Mientras todavía tenemos nodos en la cola, extraemos el primero, lo imprimimos y verificamos todos sus vecinos.

Al pasar por los vecinos, verificamos si cada uno de ellos es visitado, y si no, los agregamos a la cola y los marcamos como visitados:

Cola de pasos visitada


Agregar nodo de inicio 0 [0] {0} Visite 0, agregue 1 y 2 a la cola [1, 2] {0} Visita 1, agrega 4 a la cola [2, 4] {0, 2} Visite 2, agregue 3 a la cola [4, 3] {0, 1, 2} Visita 4, no hay vecinos no visitados [3] {0, 1, 1, 4} Visita 3, sin vecinos no visitados [ ] {0, 1, 2, 4, 3}

Complejidad del tiempo {#complejidad del tiempo}

Durante Breadth-First Traversal, cada nodo se visita exactamente una vez, y cada rama también se ve una vez en el caso de un gráfico dirigido, es decir, dos veces si el gráfico es * sin dirección*. Por lo tanto, la complejidad temporal del algoritmo BFS es O(|V| + |E|), donde V es un conjunto de nodos del gráfico y E es un conjunto formado por todas sus ramas (aristas).

Conclusión

En esta lección, hemos explicado la teoría detrás del algoritmo Breadth-First Search y hemos definido sus pasos.

Hemos representado la implementación de Python de Breadth-First Search y Breadth-First Traversal, y los probamos en gráficos de ejemplo para ver cómo funcionan paso a paso. Finalmente, hemos explicado la complejidad temporal de este algoritmo.

Licensed under CC BY-NC-SA 4.0