Gráficos en Python: Algoritmo BFS (búsqueda primero en amplitud)

Introducción

Los gráficos son una de las estructuras de datos más útiles. Se pueden usar para modelar prácticamente cualquier cosa, siendo las relaciones de objetos y las redes las más comunes. Una imagen se puede representar como un gráfico de píxeles en forma de cuadrícula y las oraciones se pueden representar como gráficos de palabras. Los gráficos se utilizan en varios campos, desde la cartografía hasta incluso la psicología social y, por supuesto, son muy utilizados en informática.

Debido a su uso generalizado, la búsqueda y el recorrido de gráficos desempeñan un papel computacional importante. Los dos algoritmos fundamentales, complementarios e introductorios utilizados para buscar y atravesar gráficos son Primera búsqueda en profundidad (DFS) y Búsqueda de amplitud (BFS).

Si desea obtener más información sobre la búsqueda primero en profundidad, lea nuestros gráficos en Python: ¡Algoritmo de búsqueda primero en profundidad (DFS)!

En este artículo, repasaremos la teoría detrás del algoritmo y la implementación de Python de Búsqueda y recorrido primero en amplitud. En primer lugar, nos centraremos en búsqueda de nodosantes de zambullirse recorrido del gráfico usando el algoritmo BFS, como las dos tareas principales para las que puede usarlo.

Notar: Asumimos un grafo implementado por lista de adyacencia en la guía.

Primera búsqueda en amplitud - Teoría

Búsqueda de amplitud (BFS) recorre sistemáticamente el gráfico, nivel por nivelformando un árbol BFS en el 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 de nudo v (estos son nodos secundarios, en primer nivel), en el orden que se muestra en la lista de adyacencia. Luego toma los nodos secundarios de esos vecinos (nivel dos) en consideración, y así sucesivamente.

Este algoritmo se puede utilizar tanto para el gráfico cruce y buscar. Al buscar un nodo que satisfaga una determinada condición (nodo de destino), la ruta con el distancia más corta desde el nodo de inicio hasta el nodo de destino. La distancia se define como el número de ramas recorridas.

BFS animado

Búsqueda extendida primero se puede usar 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.

Aunque no es el algoritmo más eficiente para resolver grandes laberintos y acertijos, y se ve eclipsado por algoritmos como el Algoritmo de Dijkstra y A*, sigue desempeñando un papel importante en el grupo y, dependiendo del problema a resolver, DFS y BFS pueden superar sus primos heurísticos.

Si desea saber más sobre el algoritmo de Dijkstra o A*, lea nuestros Gráficos en Python: Algoritmo de Dijkstra y Gráficos en Python: ¡Algoritmo de búsqueda A*!

Búsqueda en amplitud - Algoritmo

Cuando implementamos BFS, normalmente usamos un FIFO estructura como un Queue para almacenar los nodos que serán visitados a continuación.

Notar: para usar un Queue en Python, necesitamos importar el correspondiente Queue clase de la queue módulo.

Debemos tener cuidado de no caer en bucles infinitos revisando los mismos nodos una y otra vez, lo que puede suceder fácilmente con gráficos que tienen rondas. Teniendo esto en cuenta, haremos un seguimiento de los nodos que se han visitó. Esta información no necesita ser registrada explícitamente, simplemente podemos hacer un seguimiento de relativo nudos, para que no volvamos accidentalmente a él 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 al Queue.
  2. Para cada nodo, indique que no tienen un nodo padre definido.
  3. Hasta el Queue esta vacio:
    • Extraiga el nodo desde el principio de la Queue.
    • Realizar procesamiento de salida.
    • Para cada vecino del nodo actual que no es así tiene un padre definido (no se visita), agréguelo a la Queuey establecer el nodo actual como padre.

Procesamiento de salida se realiza dependiendo del propósito detrás de la búsqueda del gráfico. Al encontrar un nodo de destino, el procesamiento de salida normalmente prueba si el nodo actual es igual al nodo de destino. ¡Este es el paso en el que puedes ser creativo!

Implementación de búsqueda extendida primero: búsqueda de nodo de destino

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

Con esto en mente y considerando los pasos del algoritmo, podemos implementarlo. Definiremos un Graph class para "envolver" la implementación de 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 esta clase:

from queue import Queue

class Graph:
    
    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)
		
        
        self.m_directed = directed
		
        
        
        self.m_adj_list = {node: set() for node in self.m_nodes}      
	
    
    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))
    
    
    def print_adj_list(self):
    for key in self.m_adj_list.keys():
        print("node", key, ": ", self.m_adj_list[key])

Después de configurar un embalaje class, podemos implementar la búsqueda BFS como uno de sus métodos:

def bfs(self, start_node, target_node):
    
    visited = set()
    queue = Queue()

    
    queue.put(start_node)
    visited.add(start_node)
    
    
    parent = dict()
    parent[start_node] = None

    
    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 = []
    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 reconstruimos la ruta (si la encontramos), retrocedemos desde el nodo de destino, a través de sus padres, hasta el nodo de inicio. Además, nosotros contrarrestar el camino de nuestra propia intuición para ir de start_node hacia la target_nodesin embargo, este paso es opcional.

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

Teniendo en cuenta la implementación explicada anteriormente, podemos probarla ejecutando la búsqueda BFS en el gráfico de muestra:

gráfico de búsqueda

Consulte nuestra guía útil y práctica para aprender Git, con las mejores prácticas, los estándares aceptados por la industria y la hoja de trucos incluida. Deja de buscar en Google los comandos de Git y, de hecho, aprender ¡esta!

Vamos a recrear este gráfico usando nuestro Graph clasificar. Es un grafo no dirigido con 6 nodos, por lo que lo instanciaremos de la siguiente manera:

graph = Graph(6, directed=False)

A continuación, necesitamos agregar todos los bordes del gráfico a la instancia del Graph clase que creamos:

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 el Graph class representa internamente nuestro gráfico de muestra.

graph.print_adj_list()

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

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 comprendemos cómo se almacena como una matriz de adyacencia. Con todo esto en mente, podemos realizar una búsqueda en sí. Supongamos que nos gustaría buscar nodo 5 empezando con nodo 0:

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

Ejecutar este código da:

[0, 3, 5]

Después de echar un vistazo rápido al gráfico de muestra, podemos ver que el camino más corto entre 0 y 5 este En efecto [0, 3, 5]. Sin embargo, también puede cruzar [0, 2, 5] y [0, 4, 5]. Estos caminos alternativos son básicamente la misma distancia que [0, 3, 5] - sin embargo, considere cómo BFS compara los nodos. Se "barre" de de izquierda a derecha y 3 es el primer nodo en el lado izquierdo de la lista de adyacencia que conduce a 5por lo tanto, se toma este camino en lugar de los otros.

Esta es una característica de BFS que querrá esperar. Buscará de izquierda a derecha y hábito encuentre una ruta que también sea válida si es "después" de la primera.

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

Así es como se ve un gráfico fuera de línea:

gráfico fuera de línea

Si tuviéramos que intentar realizar una búsqueda de un camino entre los nodos 0 y 3 en este gráfico, esta búsqueda fallaría y se devolvería una ruta vacía.

Implementación primero en amplitud - Gráfico transversal

Ancho de cruce primero es un caso especial de Breadth-First Search que cruza el juntos gráfico, en lugar de buscar un nodo de destino. El algoritmo sigue siendo el mismo que definimos antes, con la diferencia de que no verificamos un nodo de destino y no necesitamos encontrar una ruta hacia él.

Esto simplifica enormemente la implementación: imprimamos cada nodo atravesado para tener una idea de cómo atraviesa los nodos:

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)  

Notar: Este método debe implementarse como parte del Graph clase implementada antes.

Ahora definamos el siguiente gráfico de muestra como se mostró anteriormente:

gráfico de curso



graph = Graph(5, directed=False)


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:

graph.bfs_traversal(0)

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

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. Cuando comenzamos la poligonal desde el nodo inicial 0se pone en el visited juntos y en queue así como también. Aunque todavía tenemos nudos en el queueextraemos el primero, lo imprimimos y verificamos todos sus vecinos.

Pasando por los vecinos, comprobamos si cada uno de ellos es visitado, y si no los agregamos a la queue y marcarlos como visitados:

No Cola Visitó
Agregar nodo inicial 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}
Visita 2, agrega 3 a la cola [4, 3] {0, 1, 2}
Visita 4, sin vecinos no visitados [3] {0, 1, 1, 4}
Visita 3, sin vecinos no visitados [ ] {0, 1, 2, 4, 3}

Complejidad temporal

Durante Ancho de cruce primerocada nodo es visitado exactamente una vez quey cada rama también se visualiza una vez que en caso de dirigido gráfica, es decir dos veces si el gráfico es no dirigido. Por lo tanto, la complejidad temporal del algoritmo BFS es O(|V| + |E|)o V es un conjunto de nodos del grafo, y mi es un conjunto formado por todas sus ramas (aristas).

Conclusión

En esta guía, explicamos la teoría detrás del algoritmo Breadth-First Search y definimos sus pasos.

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

Si quieres conocer otros artículos parecidos a Gráficos en Python: Algoritmo BFS (búsqueda primero en amplitud) puedes visitar la categoría Código.

Deja un comentario

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

Subir

Esta página web utiliza cookies para analizar de forma anónima y estadística el uso que haces de la web, mejorar los contenidos y tu experiencia de navegación. Para más información accede a la Política de Cookies . Ver mas