búsqueda por anchura en un grafo (BFS)
2 4 8
s 5 7
3 6 9
PROCEDIMIENTO
o Dado un vértice fuente s, Breadth-first search sistemáticamente explora los vértices de G para “descubrir”
todos los vértices alcanzables desde s.
o Calcula la distancia (menor número de vértices) desde s a todos los vértices alcanzables.
o Después produce un árbol BF con raíz en s y que contiene a todos los vértices alcanzables.
o El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más
corto medido en número de vértices.
o Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a
los nodos de distancia k, sólo tras haber llegado a todos los nodos a distancia k-1.
1
búsqueda por anchura en un grafo (BFS)
ALGORITMO
2
búsqueda por anchura en un grafo (BFS)
la ruta más corta
1
desde s
2 4 8
0 s 5 7
3 6 9
Undiscovered
Discovered cola: s
Top of queue
Finished
3
búsqueda por anchura en un grafo (BFS)
1
2 4 8
0 s 5 7
3 6 9
Undiscovered
Discovered cola: s 2
Top of queue
Finished
4
búsqueda por anchura en un grafo (BFS)
1
2 4 8
0 s 5 7
1
3 6 9
Undiscovered
Discovered cola: s 2 3
Top of queue
Finished
5
búsqueda por anchura en un grafo (BFS)
1
2 4 8
0 s 5 7
1
3 6 9
Undiscovered
Discovered cola: 2 3 5
Top of queue
Finished
6
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
Undiscovered
Discovered cola: 2 3 5
Top of queue
Finished
7
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
5 ya ha sido descubierto:
0 s 5 7
no poner en cola
1
3 6 9
Undiscovered
Discovered cola : 2 3 5 4
Top of queue
Finished
8
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
Undiscovered
Discovered cola : 2 3 5 4
Top of queue
Finished
9
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
Undiscovered
Discovered cola : 3 5 4
Top of queue
Finished
10
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
1 2
Undiscovered
Discovered cola : 3 5 4
Top of queue
Finished
11
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
1 2
Undiscovered
Discovered cola : 3 5 4 6
Top of queue
Finished
12
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
1 2
Undiscovered
Discovered cola : 5 4 6
Top of queue
Finished
13
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
1 2
Undiscovered
Discovered cola : 5 4 6
Top of queue
Finished
14
búsqueda por anchura en un grafo (BFS)
1 2
2 4 8
0 s 5 7
1
3 6 9
1 2
Undiscovered
Discovered cola : 4 6
Top of queue
Finished
15
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1
3 6 9
1 2
Undiscovered
Discovered cola : 4 6
Top of queue
Finished
16
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1
3 6 9
1 2
Undiscovered
Discovered cola : 4 6 8
Top of queue
Finished
17
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2
Undiscovered
Discovered cola : 6 8
Top of queue
Finished
18
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 6 8 7
Top of queue
Finished
19
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 6 8 7 9
Top of queue
Finished
20
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 8 7 9
Top of queue
Finished
21
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 7 9
Top of queue
Finished
22
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 7 9
Top of queue
Finished
23
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 7 9
Top of queue
Finished
24
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 7 9
Top of queue
Finished
25
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 9
Top of queue
Finished
26
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 9
Top of queue
Finished
27
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola : 9
Top of queue
Finished
28
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Undiscovered
Discovered cola :
Top of queue
Finished
29
búsqueda por anchura en un grafo (BFS)
1 2 3
2 4 8
0 s 5 7
1 3
3 6 9
1 2 3
Nivel Gráfico
30
