¿Qué es una primera búsqueda amplia?

La primera búsqueda de amplitud es un algoritmo de recorrido de gráficos en el que el nodo fuente se expande primero y luego los vecinos del nodo fuente se expanden a continuación, luego los vecinos de los vecinos y así sucesivamente.

El primer algoritmo de búsqueda de amplitud es una instancia del algoritmo de búsqueda de gráficos.

Inicialmente, la cola solo contiene el vértice de origen y se marca como se ve.

Luego repita los siguientes pasos hasta que la cola esté vacía:

1. Eliminar el nodo de la cola.
2. Busque el vértice no visitado del nodo eliminado. inserte el nodo no visitado en la cola y marque como visitado.

Pseudocódigo

BFS (g, s)
crear una cola Q
Q.encueue (s)
marque s como visitado.

while (Q no está vacío)

v = Q.dequeue () // elimina el elemento superior

para todos los vecinos w de v en el Gráfico G
si no se visita w
Q.enqueue (w)
marque w como visitado.

Explicación: Programmingz [1]

Notas al pie

[1] Algoritmo de gráfico BFS (con código en C, C ++, Java y Python)

Imagina un árbol. Comienza desde un solo nodo raíz, luego cada nodo tiene dos hijos. Cada nodo tiene un número escrito en él. Ahora, pregunto, ¿qué nodo tiene el número 57? En la búsqueda de amplitud primero, verifica la raíz, luego los hijos, luego los nietos, etc. En cada profundidad, buscas en todos los hermanos. En la búsqueda de profundidad primero, busca el primer hijo, luego su primer hijo, y así sucesivamente por el borde de la estructura del árbol hasta que no pueda profundizar más, y solo entonces comienza a verificar a los hermanos.

Si está buscando en una estructura jerárquica, significa que buscará una coincidencia en todos los elementos de un nivel antes de pasar al siguiente nivel.

Por supuesto, Wikipedia también lo sabe:

Búsqueda de amplitud

Es cuando primero busca a sus vecinos, luego a los vecinos de sus vecinos, luego a los vecinos de sus vecinos, etc., en ese orden.