> For the complete documentation index, see [llms.txt](https://ooi.gitbook.io/courses/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ooi.gitbook.io/courses/ooi-2020/cursos-avanzados/untitled-1.md).

# Sesión 21

## Curso final de la OOI 2020

### Sesión 21

Fecha: 26 de mayo de 2020.

## Temas

BFS (Breadth First Search) (Búsqueda en amplitud)

* Explora los nodos en orden nivel por nivel.
* Utiliza una cola para saber el orden de los nodos a visitar.
* El nodo representa el estado de la búsqueda.

![Comparación de cómo se recorre el árbol para una DFS y BFS](/files/-M9JaHaDpRzOo8ukxhub)

![Simualación de recorrido de una DFS y BFS en un laberinto](/files/-M9JakCVpXzAFwF7rsI2)

### Algoritmo de la BFS

```c
Crear una cola vacia
Insertar el primer nodo a la cola
while la cola no este vacia
    Sacar el primer nodo de la cola
    Marcar este nodo como visitado
    if este nodo es la respuesta
        respuesta_encontrada = true
        break // terminar con la busqueda
    else
        for cada hijo del nodo
            if nodo no visitado
                agregar a la cola
if cola vacia and !respuesta_encontrada
    // no se encontro respuesta
```

```cpp
Nodo bfs(Nodo inicio) {
    queue<Nodo> Q;
    Q.push(inicio);

    while(!Q.empty()) {
        Nodo actual = Q.front();
        Q.pop();
        if (es_respuesta(actual)) {
            return actual; // Regresar el estado donde se encontro la respuesta.
        }
        visitado[actual.x][actual.y] = true;

        // Probar con todos los hijos.
        for (int i = 0; i < numHijos; i++) {
            Nodo sig;
            sig = // asignar los valores correspondientes al nodo siguiente.
            if(es_valido(sig)) {
                Q.push(sig);
            }
        }
    }
    return -1;
}
```

## Ejercicios

### Búsqueda en amplitud (BFS)

Encuentra la cantidad mínima de pasos que se tienen que dar para ir del punto de inicio al final.

```
10 10
XXXXXXXXXX
X.....I..X
X...XXXXXX
X.X......X
X.XXXXX..X
X.X...X..X
X.X.F.XX.X
X..X.....X
X..X.....X
XXXXXXXXXX

SI
```

```
10 10
XXXXXXXXXX
X.....I..X
X...XXXXXX
X.X......X
X.XXXXX..X
X.X...X..X
X.X.F.XXXX
X..X.....X
X..X.....X
XXXXXXXXXX

NO
```

### Códigos vistos en clase

{% embed url="<https://github.com/omioaxaca/ooi-2020/tree/master/curso-avanzado/sesion-21>" %}

{% hint style="success" %}
**Video**: <https://www.youtube.com/watch?v=lbS5FBNpUNk>
{% endhint %}