¿Cuál es el significado de 'amplitud' en la primera búsqueda de amplitud?

Estaba aprendiendo sobre la primera búsqueda de amplitud y se me ocurrió una pregunta de por qué BFS se llama así. En el libro Introducción a los algoritmos de CLRS , leí la siguiente razón para esto:

La búsqueda de amplitud primero se llama así porque expande la frontera entre vértices descubiertos y no descubiertos de manera uniforme a lo largo de la frontera.

Sin embargo, no puedo entender el significado de esta declaración. Estoy confundido acerca de esta palabra "frontera" y la amplitud de esa frontera.

Entonces, ¿alguien puede responder esta pregunta de una manera que sea fácil de entender para un principiante como yo?

Considere la estructura de datos utilizada para representar la búsqueda. En un BFS, usa una cola. Si se encuentra con un nodo invisible, lo agrega a la cola.

La "frontera" es el conjunto de todos los nodos en la estructura de datos de búsqueda. La cola iterará a través de todos los nodos en la frontera secuencialmente, iterando así a lo ancho de la frontera. DFS siempre mostrará el estado descubierto más recientemente fuera de la pila, por lo que siempre iterará sobre la parte más profunda de la frontera.

Considera la imagen de abajo. Observe cómo el DFS va directo a las partes más profundas del árbol, mientras que el BFS itera sobre la amplitud de cada nivel.

Imagen aqui

La cita que da dice "la frontera entre vértices descubiertos y no descubiertos". Esa es la frontera de la que habla el autor: la frontera entre vértices descubiertos y no descubiertos. Tienes algunos vértices que todavía no has visto nada. También tienes algunos vértices para los que has visto todo. Y luego tienes vértices en el medio. Estos son vértices que has visto, pero aún no has cargado a todos sus hijos. Esta es la frontera.

Discute esto más adelante en:

Para realizar un seguimiento del progreso, BFS colorea cada vértice de blanco, gris o negro. Todos los vértices comienzan en blanco y luego pueden volverse grises y luego negros. El vértice se descubre la primera vez que se encuentra durante la búsqueda, momento en el que se vuelve no blanco. Por lo tanto, se han descubierto vértices grises y negros, pero BFS distingue entre ellos para garantizar que la búsqueda se realice de manera BF.
...
cada vértice es inicialmente blanco, está atenuado cuando se descubre en la búsqueda y se oscurece cuando está terminado, es decir, cuando su lista de adyacencia se ha examinado por completo.

Entonces todos los vértices comienzan en blanco (sin descubrir). Cuando se descubre un nodo, es de color gris (frontera). Cuando todo lo que señala ha sido descubierto, es de color negro (completamente descubierto). La frontera es el conjunto de puntos que se han descubierto, pero que han descubierto niños.

Supongamos que está buscando algo en el sitio web. Primero vas a la página principal. Supongamos que eso está etiquetado como "animales". La frontera es actualmente {"animales"}. Miras a través de la página principal y no ves lo que estás buscando. Pero se da cuenta de que tiene enlaces a dos páginas más, "cuadrúpedos" y "gusanos". Entonces haces clic en el enlace a "cuadrúpedos". Ahora la frontera es {"animales", "cuadrúpedos"}. Miras a través de "cuadrúpedos" y no encuentras lo que estás buscando. ¿Qué vas a hacer después? Puede buscar enlaces en "cuadrúpedos" y seguirlos, o volver a "animales" y hacer clic en el enlace a "gusanos". La primera es una búsqueda de profundidad primero, y la segunda es una búsqueda de amplitud.

"profundidad" se refiere a cuántos enlaces del nodo raíz se necesita para llegar a un nodo, mientras que "amplitud" se refiere a los nodos como la misma profundidad. En el ejemplo anterior, BFS comienza en "animales" y primero mira todos los nodos de profundidad uno, por lo que primero mira "cuadrúpedos" y "gusanos". Después de haber examinado todos los nodos de profundidad 1, expande la frontera a través de todos esos nodos; es decir, observa a los hijos de todos los nodos de profundidad 1 antes de mirar a cualquiera de los nodos de profundidad-2. Entonces, por ejemplo, si uno de los enlaces en la página de "cuadrúpedos" es "primates", examinará todos los enlaces en la página de "gusanos" antes de ver cualquiera de los enlaces en la página de "primates".

Supongamos que el algoritmo BFS se ejecuta a partir del vértice . Imagine una ola que se envía desde (como una ola de agua o un tsunami). Después de un paso de tiempo, la ola habría alcanzado a todos los vecinos de . Después de dos pasos de tiempo, la onda habría alcanzado (o "visitada") todos los vértices que se encuentran a distancia como máximo de . Y así. $a$$a$$a$$2$$a$

En cualquier momento, la frontera de la onda son exactamente los vértices que se almacenan en la estructura de datos de la cola (estos vértices se han visitado pero aún no se han explorado más).

Por lo tanto, la onda alcanza inicialmente toda la "amplitud" de todos los vértices que se encuentran a la distancia 1 de . Después de algunos pasos de tiempo, la ola habría cubierto todo el ancho hasta cierta distancia desde el punto de partida . $a$$a$

El conjunto de vértices a la distancia de se llama la capa en la partición de distancia de la gráfica con respecto al vértice . El conjunto de vértices es la unión disjunta de estas capas . La capa es , la primera capa es el conjunto de vecinos de , la segunda capa es el conjunto de vértices cuya distancia a es dos, y así sucesivamente. El algoritmo BFS visita los vértices del gráfico en un orden particular, capa por capa. Cada capa cubre toda la amplitud, pero las diferentes capas tienen una profundidad diferente.$k$$a$$k$$a$$(k \ge 0)$$0$$\{a\}$$a$$a$

Por otro lado, el algoritmo DFS exploraría lo más profundo posible en una dirección (es decir, visitar 's primer vecino, entonces su vecino, entonces su vecino, etc.) antes de regresar de nuevo a y visitar el vecino inexplorada de . Este algoritmo se profundiza primero, en lugar de visitar a los vecinos en términos de amplitud. $a$$a$$a$

Por lo tanto, DFS y BFS difieren en el orden en que visitan los vértices.