BREADTH-FIRST SEARCH

Método

Breadth-First Search es una manera de encontrar todos los vértices alcanzables desde el origen de un vértice dado, s. Al igual que la primera búsqueda de profundidad, BFS atraviesa un componente conexo de un grafo dado, y define un árbol de expansión. Intuitivamente, la idea básica del primer aliento de la búsqueda es la siguiente: enviar una onda a cabo desde la fuente s. La ola golpea todos los vértices de un borde de s. A partir de ahí, la ola golpea todos los vértices y los dos bordes de s. el uso de colas FIFO 'Q' para mantener el frente de onda: v es en Q si y sólo si la onda ha afectado v, pero no ha salido de v todavía.

Algoritmo

Estrategia Global del Algoritmo

Breadth-first search comienza en un vértice dado s, que es en el nivel 0. En la primera etapa, que visita todos los vértices que están en la distancia de un borde de distancia. Cuando visitamos allí, pintamos como "visitado", los vértices adyacentes al iniciar el vértice s - estos vértices se sitúan en el nivel 1. En la segunda etapa, visitamos todos los nuevos vértices, podemos llegar a la distancia de los dos bordes de distancia desde el vértice fuente s. Estos nuevos vértices, que son adyacentes al nivel 1 vértices y no asignados previamente a un nivel, se colocan en el nivel 2, y así sucesivamente. El recorrido BFS termina cuando cada vértice ha sido visitado.Para realizar un seguimiento de los progresos, Breadth-first search colorea cada vértice. Cada vértice de la gráfica se encuentra en uno de tres estados:

1. Sin descubrir.
2. Date a conocer, pero no totalmente exploradas.
3. Explorado a fondo.

El estado de un vértice, u , se almacena en una variable de color de la siguiente manera:

1. color [ u ] = Blanco - para el "desconocido" del Estado,
2. color [ u ] = gris - para el "descubierto, pero no completamente explorado" el estado, y
3. color [ u ] = Negro - para el "explorado" el estado.

El BFS (G, s) desarrolla un algoritmo de búsqueda primero de árboles amplitud con el vértice origen, s, como su raíz. El padre o el antecesor de cualquier otro vértice en el árbol es el vértice de la que fue descubierto por primera vez. Para cada vértice v, el padre de v se coloca en la variable π [v]. Otra variable, d [v], calculado por BFS contiene el número de aristas del árbol en el camino de s a v.

Breadth-first search utiliza una cola FIFO, Q, para almacenar vértices gris.

Algoritmo: Transversal de breadth-first search.

BFS (V, E, s )

1. para cada u en V - { s } ▷ para cada vértice u en V [G], excepto s.
2. hacer de color [ u ] ← BLANCO.
3. d [ u ] ← infinito.
4. π [ u ] ← NIL.
5. color [ s ] ← GRIS vértice Fuente ▷ descubierto.
6. d [ s ] ← 0 ▷ inicializar.
7. π [ s ] ← NIL ▷ inicializar.
8. Q ← {} ▷ Borrar la cola Q.
9. Poner en cola (Q, s).
10 , mientras que Q es no vacío.
11. hacer u ← quitar de la cola (Q) ▷ Es decir, u = cabeza [Q].
12. para cada v adyacente a u ▷ de bucle por cada nodo a lo largo con el .borde.
13. hacer si el color [v] ← BLANCO ▷ si el color es el blanco que nunca has visto antes.
14. continuación, color [v] ← GRIS
15. d [v] ← d [u] + 1.
16. π [v] ← u.
17. Poner en cola (Q, v).
18. Quitar de la cola (Q).
19. color [u] ← NEGRO.

Evaluación

Ejemplo: La siguiente figura (de CLR) ilustra el progreso de la búsqueda en amplitud de sesiones en el gráfico de la muestra sin dirección.

a. Después de la inicialización (pintar cada vértice blanco, conjunto d [u] hasta el infinito para cada vértice u, y establecer que el padre de cada vértice a ser el NIL), el vértice de origen se descubre en la línea 5. Líneas 8-9 inicializar Q para contener sólo el vértice fuente
s.

b. El algoritmo descubre todos los vértices de un borde de s, es decir, descubrir todos los vértices (w y r) en el nivel 1.

c.

d. El algoritmo descubre todos los vértices dos bordes de la s, es decir, descubrir todos los vértices ( t , x , y v ) en el nivel 2.

e.

f.

g. El algoritmo descubre todos los vértices 3 aristas de s, es decir, descubrir todos los vértices (u y y) en el nivel 3.

h.

i. El algoritmo termina cuando todos los vértices se ha explorado completamente.

Análisis

• El bucle while en la búsqueda primero en amplitud se ejecuta en la mayoría de | veces | V. La razón es que cada vértice en cola en la mayoría de una sola vez. Por lo tanto, tenemos O (V).

• El ciclo for dentro del bucle while se ejecuta en la mayoría de | E | veces si G es un grafo dirigido o 2 | E | veces si G es no dirigido. La razón es que cada vértice desencolan en más de una vez y examinamos ( u , v ) sólo cuando u es quitado de la cola. Por lo tanto, cada arista examinados más de una vez si se dirige, a lo sumo dos veces si no dirigido. Por lo tanto, tenemos O (E).

Por lo tanto, el tiempo total acumulado de recorrido de la búsqueda primero en amplitud es O (V+E).