1 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. 1) Se marcan todos los nodos como NO visitados. 2) Se marca y se visita S (nodo distinguido). 3) Se pone a S en la cola (queue). 4) Mientras la cola no este vacía: 5) Se quita el primero de la cola, y se toma como nodo actual. 6) Para cada vecino del nodo actual, vea : Si ese vecino no esta marcado, entonces se visita y se marca el vecino. Se actualiza el valor dist[] del vecino y se pone el vecino en la cola.

2 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. 1) Se marcan todos los nodos como NO visitados. F A BC G DE H

3 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. 2) Se marca y se visita S=A (nodo distinguido). F A BC G DE H visitado(A)

4 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. 3) Se pone A (nodo distinguido) en la cola. F A BC G DE H Queue: A get 0 visitado(A)

5 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. 4) Mientras la cola no este vacía: F A BC G DE H Queue: A 0

6 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). F A BC G DE H visita(F) Queue: 1 0

7 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H visita(B) Queue: F 1 1 0 En plena etapa 6).

8 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H visita(C) Queue: FB 11 1 0 En plena etapa 6).

9 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H visita(G) Queue: FBC 0 1 11 1 En plena etapa 6).

10 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H procesado(A) Queue: FBCG 0 1 11 1 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). get

11 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: BCG 0 1 11 1 En plena etapa 6). 2

12 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: BCGD 0 1 11 1 En plena etapa 6). 22

13 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: BCGDE 0 1 11 1 22 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). procesado(F) get

14 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: CGDE 0 1 11 1 22

15 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: CGDE 0 1 11 1 22 ya fue visitado

16 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: CGDE 0 1 11 1 22 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). get procesado(B)

17 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: GDE 0 1 11 1 22 ya fue visitado

18 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: GDE 0 1 11 1 22 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). procesado(C) get

19 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: DE 0 1 11 1 22 ya fue visitado

20 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: DE 0 1 11 1 22 ya fue visitado

21 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: DE 0 1 11 1 22 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). get procesado(G)

22 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: E 0 1 11 1 22 ya fue visitado

23 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: E 0 1 11 1 22 ya fue visitado

24 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: E 0 1 11 1 22 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). procesado(D) get

25 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: 0 1 11 1 22 ya fue visitado

26 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: 0 1 11 1 22 ya fue visitado

27 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: 0 1 11 1 22 ya fue visitado

28 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: 0 1 11 1 22 3

29 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: H 0 1 11 1 22 5) Se quita el primero de la cola, y se toma como nodo actual, pasando a ejecutar la etapa 6). 3 procesado(E) get

30 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: 0 1 11 1 22 3 ya fue visitado

31 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H Queue: 0 1 11 1 22 Se han terminado de procesar todos los nodos. 3 procesado(H) Pare

32 Dr. Eric Jeltsch F. Ing. en Computación, ULS, DAA_04 Breadth-First Search(BFS) para grafos no dirigidos. F A BC G DE H 0 1 11 1 22 3