Utiliza una cola para saber el orden de los nodos a visitar.
El nodo representa el estado de la búsqueda.
Algoritmo de la BFS
Crear una cola vaciaInsertar el primer nodo a la colawhile la cola no este vacia Sacar el primer nodo de la cola Marcar este nodo como visitadoif este nodo es la respuesta respuesta_encontrada =truebreak // terminar con la busquedaelsefor cada hijo del nodoif nodo no visitado agregar a la colaif cola vacia and !respuesta_encontrada// no se encontro respuesta
Nodobfs(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.
