Algoritmo de búsqueda en amplitud

Vista previa del material en texto

Algoritmo de búsqueda en amplitud (BFS)
El algoritmo de búsqueda en amplitud (BFS, por sus siglas en inglés) es un algoritmo utilizado para recorrer o buscar en un grafo. Este algoritmo comienza en un nodo raíz dado y explora todos los nodos vecinos al nodo actual antes de moverse a los nodos vecinos de esos nodos. Es decir, explora primero todos los nodos a una profundidad dada antes de moverse a los nodos de la siguiente profundidad.
El algoritmo de BFS se implementa utilizando una estructura de datos conocida como cola (queue en inglés). En cada paso del algoritmo, se encolan todos los vecinos del nodo actual y luego se desencola el siguiente nodo a explorar. Este proceso continúa hasta que se han explorado todos los nodos alcanzables desde el nodo raíz.
El algoritmo de BFS es especialmente útil para encontrar el camino más corto entre dos nodos en un grafo no ponderado, ya que garantiza que el primer camino encontrado es el más corto.