Pitón BFS

La búsqueda en el campo de la programación se divide principalmente en dos tipos, búsqueda primero en profundidad (DFS) y búsqueda primero en amplitud (BFS). Estos son los algoritmos de búsqueda utilizados para buscar o recorrer el gráfico.

La búsqueda primero en amplitud es el fenómeno de atravesar cada nodo del gráfico o árbol, de modo que cada nodo es atravesado por dos partes. Una es la parte «visitada» y la otra es la parte «no visitada». Esto significa que esta búsqueda tiene como objetivo llegar a todos los nodos del gráfico.

Pseudocódigo BFS y algoritmo

• El primer paso es agregar cualquier primer nodo de origen desde el final de la cola.
• Cree la lista o matriz visitada y luego inserte los nodos en ella.
• Use un bucle while para verificar que la cola no esté vacía y luego siga eliminando elementos de la lista visitada.
• Todos los elementos eliminados se marcan como visitados y ahora también eliminan los vecinos no visitados de la cola.

Aplicaciones de BFS

• Se utiliza para la navegación GPS.
• Se utiliza para encontrar el camino.
• Se utiliza para crear el índice por índice de búsqueda.
• Implementación de BFS.

Ejemplo 1

Primero presentamos el gráfico; queremos tener los valores para iterar. Cada nodo todavía contiene los valores. Aquí, por ejemplo, el primer número 5 está conectado a los dos nodos 3 y 7. Asimismo, todos los demás números están conectados a otros nodos para formar un gráfico. Después de definir el gráfico, incluimos dos tipos de datos enteros de matriz para almacenar los valores numéricos del gráfico que se visitarán. Mientras que el otro contiene aquellos nodos que son adyacentes a los visitados.

Ambas matrices están vacías en el momento en que se inicia la búsqueda en anchura. Pero poco a poco, estos arreglos contienen los valores de los nodos, como describimos en el gráfico.

Habiendo introducido dos matrices, definamos una función para acceder a todos los nodos y buscarlos fila por fila. Esta función toma los valores del arreglo visitado, el grafo y el tercero es el nodo. Dentro de la función agregaremos valores en ambas matrices como se describe en el algoritmo; Primero se ingresan los valores en la ‘Cola’; cuando se visita, ese nodo en particular se transfiere a la cola visitada. Entonces, ahora mismo, esta función agrega los valores en las matrices usando una función de adición para cada matriz. Esta función contiene los nodos como parámetros dentro de sí misma.

Después de eso, ahora accederemos y visitaremos los nodos a través de un enfoque. Esta forma de acceder a los nodos es similar a acceder a las matrices en el sentido de que siempre usamos un bucle para visitar iterativamente cada índice. En el caso de bfs, usamos un ciclo while, y dentro de este ciclo while, se agrega un ciclo for para satisfacer la condición utilizada por el ciclo while.

Este bucle while apunta directamente a la cola, ya que los nodos se agregan primero a la cola y luego a la matriz visitada. Los valores son extraídos por la función pop() y almacenados en las variables apropiadas.

Este valor se muestra cuando se activa la función de impresión. Ahora, al extraer los valores de la cola, este valor se usa para ubicar a sus vecinos para poner en cola. Así que aquí usaremos un ciclo for para asignar cada vecino al final del gráfico. La condición aplicada aquí es que si el valor no está en la matriz visitada, significa que no se accedió antes, la matriz visitada se agregará con estos nuevos valores (vecino) a través de la función de agregar. Y de manera similar, la cola también obtiene el valor de los nuevos vecinos.

Visitado. Adjuntar (vecino)

La llamada a la función se realiza junto con el arreglo visitado, el grafo completo y el nodo como parámetros.

Bfs (visitado, gráfico, ‘5’)

Después de usar este código, puede ver la salida relevante a través de la consola resultante usando el botón ejecutar en la parte superior de la barra de herramientas.

Puede ver que se accede a toda la ruta a través de los nodos. Una cosa para observar aquí: todos estos nodos de inicio solo se muestran porque estos nodos se sacan de la cola antes de la función de impresión cada vez.

ejemplo 2

Este ejemplo usa la misma técnica: buscar dentro del diagrama o un árbol. Pero aquí hemos usado el enfoque OOP (Programación Orientada a Objetos) en Python usando el sistema de clases. Primero importaremos algunas características de la biblioteca de la colección. Estas funciones incluyen el «defaultdict» que contiene el diccionario del lenguaje Python.

Volviendo a la clase, primero definimos el nombre de la clase, y dentro de la clase, aquí está el constructor. Los constructores son las funciones que se ejecutan automáticamente cuando creamos el objeto de la clase. El objeto de la clase es necesario para poder acceder a las características de la clase. También crearemos el objeto para la clase Graph más adelante en este artículo. Primero, el constructor se define aquí para inicializar la lista tomada como un gráfico.

predeterminado (lista)

«Es» se utiliza para almacenar el gráfico en el diccionario predeterminado.

Después de eso, aquí se usa una función, ‘agregada’, para agregar el nuevo nodo o borde al diagrama. Los nodos también se denominan aristas y están representados por «u», Por el contrario, la distancia entre los bordes está representada por el vértice y denotada por ‘v’. Dentro de la función, el gráfico se mantiene con nuevos nodos mediante la función de adición.

Aquí también usamos una función para mostrar el BFS de un gráfico. Inicialmente, se declaran todos los nodos ya que no se visitarán. En la primera fase de búsqueda, declaramos el estado como FALSO.

De manera similar, la cola se inicializa a cero en el momento de la creación.

Ahora hablemos del nodo fuente, que es el primero; Lo pondremos en la matriz visitada y lo extraeremos de la cola como hicimos en el primer ejemplo.

Ahora se usa un ciclo while para sacar de la cola todos los nodos y luego imprimir el valor.

Después de eso, todos los nodos del vecino vecino se extraen de la cola; si ya se visitó algún nodo, se ingresa en la cola de visitas. La declaración if se usa para verificar si el nodo aún no ha sido visitado y luego agregarlo de la cola y colocarlo en la matriz visitada.

G = graph() es de alguna manera una forma de creación de objetos del constructor y este objeto se usa además para llamar a la función agregada junto con los valores vecinos.

Conclusión

El artículo de BFS Python tiene una breve descripción del uso del gráfico de ancho primero para atravesar cada nodo. Este proceso de búsqueda se realiza teniendo dos listas que contienen los nodos visitados y no visitados dentro de ellas. Elaboramos el concepto incluyendo dos ejemplos elementales en la guía.