Bfs python
La amplitud de la primera búsqueda es el fenómeno de atravesar cada nodo del gráfico o un árbol, por lo que cada nodo está atravesado por dos partes. Uno es la porción 'visitada', y la otra es la parte 'no visitada'. Esto significa que esta búsqueda tiene como objetivo llegar a cada nodo del gráfico.
Pseudocodo y algoritmo BFS
- El primer paso es colocar cualquier nodo de primer origen en la cola desde la parte posterior.
- Crea la lista o matriz visitada y luego coloca los nodos en ella.
- Use un bucle de tiempo para verificar que la cola no esté vacía y luego siga eliminando los elementos en la lista visitada.
- Todos los elementos eliminados están marcados como se visitan y ahora también retiran a los vecinos que no están visitados de la cola también.
Aplicaciones de BFS
- Se usa para la navegación GPS.
- Se utiliza para encontrar el camino.
- Se utiliza para construir el índice por índice de búsqueda.
- Implementación de BFS.
Ejemplo 1
Primero presentamos el gráfico; Queremos tener los valores que deben ser atravesados. Cada nodo contiene más valores. Por ejemplo, aquí, el primer número 5 se conectará con los dos nodos 3 y 7. Del mismo modo, todos los demás números están conectados con otros nodos para formar un gráfico. Después de definir el gráfico, contendremos dos tipos de datos enteros de matriz para almacenar los valores numéricos del gráfico que se deben visitar. Mientras que el otro incluye los nodos que están al lado de los que se visitan.
Visitado = []Cola = []
Ambas matrices están vacías al momento de comenzar la búsqueda de amplitud. Pero gradualmente, estas matrices contienen los valores de los nodos como hemos descrito en el gráfico.
Después de introducir dos matrices, definiremos una función para acceder y buscar todos los nodos en cuanto a la línea. Esta función toma los valores de la matriz visitada, el gráfico y el tercero es el nodo. Dentro de la función, agregaremos valores en ambas matrices, como se describe en el algoritmo; Primero, los valores se ingresan dentro de la 'cola'; Cuando se visita, ese nodo en particular se transfiere a la cola visitada. Entonces, por ahora, esta función agregará los valores en las matrices utilizando una función de anexo para cada matriz. Esta función contiene los nodos como un parámetro en él.
Visitado.Añadir (nodo)Cola.Añadir (nodo)
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 matrices porque siempre aplicamos un bucle para visitar cada índice iterativamente. En el caso de BFS, usaremos un bucle de tiempo, y dentro de este bucle While, se agrega un bucle for para satisfacer la condición utilizada por el bucle while.
Este bucle While se dirigirá directamente a la cola porque los nodos se agregarán primero a la cola y luego a la matriz visitada. Entonces, los valores se extraerán a través de la función pop () y se almacenarán en variables respectivas.
M = cola. Pop (0)Este valor se mostrará en la llamada de la función de impresión. Ahora, cuando se extraen los valores de la cola, este valor se utilizará para localizar a sus vecinos que se ingresarán en la cola. Por lo tanto, usaremos para bucle aquí para asignar a cada vecino hasta el final del gráfico. La condición aplicada aquí es que si el valor no está en la matriz visitada, significa que no se ha accedido anteriormente, entonces la matriz visitada será agregada por estos nuevos valores (vecinos) a través de la función de anexo. Y de manera similar, la cola también obtendrá el valor de los nuevos vecinos.
Visitado. Anexar (vecino)
La llamada de función se realiza junto con la matriz visitada, todo el gráfico y el nodo como parámetro.
BFS (visitado, gráfico, '5')
Después de usar este código, puede ver la salida relevante a través de la consola resultante utilizando el botón de ejecución en la parte superior de la barra de herramientas.
Puede ver que se accederá a toda la ruta a través de los nodos. Aquí se puede observar una cosa: todos estos nodos iniciales se muestran solo porque cada vez antes de la función de impresión, estos nodos se salen de la cola.
Ejemplo 2
Este ejemplo funciona en la misma técnica: buscar dentro del gráfico o un árbol. Pero aquí, hemos utilizado el enfoque de OOP (programación orientada a objetos) en Python utilizando el sistema de clases. Entonces, primero importaremos algunas características de la biblioteca de colecciones. Estas características incluyen el "Defaultsdict" que contiene el diccionario en el lenguaje de Python.
Pasando hacia la clase, primero, definimos el nombre de la clase, y dentro de la clase, aquí está el constructor. Como los constructores son aquellas características que se ejecutan automáticamente a medida que creamos el objeto de la clase. El objeto de la clase es necesario para acceder a las características de la clase. También crearemos el objeto para la clase gráfica más adelante en el artículo. Primero, el constructor se define aquí para inicializar la lista tomada como un gráfico.
Defaultdict (lista)
"Se usa" para almacenar el gráfico en el diccionario predeterminado.
Después de eso, se usa una función aquí, 'agregado' para agregar el nuevo nodo o borde al gráfico. Los nodos también se conocen como bordes y están representados por 'u,.'En contraste, la distancia entre los bordes está representada por el vértice y es mencionado por' V.'Entonces, dentro de la función, el gráfico se entretendrá con nuevos nodos a través de la función de anexo.
Ser.Gráfico [u]. adjuntar (v)Aquí también hemos utilizado una función para mostrar el BFS de un gráfico. Inicialmente, todos los nodos se declaran ya que no se visitan. En la primera etapa de búsqueda, declararemos el estado como falso.
Visitado = [falso] * (max (self.gráfico) + 1)Del mismo modo, la cola se inicializa como cero en el momento de la creación.
Cola = []Hablemos ahora sobre el nodo fuente, que es el primero; Lo ingresaremos en la matriz visitada y la extraeremos de la cola como lo hicimos en el primer ejemplo.
Cola.adjuntar (s)Visitado [s] = verdadero
Ahora se usa un bucle de tiempo para desplegar todos los nodos de la cola y luego imprimirá el valor.
S = cola.Pop (0)Después de eso, todos los nodos del vecino adyacente se extraerán de la cola; Si ya se visita algún nodo, esto se ingresará en la cola visitada. Si la declaración se usa para verificar si el nodo aún no se visita, luego agéngalo desde la cola e ingrese en la matriz visitada.
G = Graph () es de alguna manera una forma de creación de objetos del constructor, y este objeto se usa aún más para llamar a la función agregada junto con los valores del vecino.
Conclusión
El artículo 'BFS-Python' contiene una breve descripción de la búsqueda de amplitud primera en el gráfico para atravesar cada nodo. Este proceso de búsqueda se realiza teniendo dos listas que contienen los nodos visitados y no visitados en ellos. Hemos elaborado el concepto agregando dos ejemplos elementales en la guía.