Búsqueda en anchura

En Ciencias de la Computación, Búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo de búsqueda no informada utilizado para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles).

Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo.

A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.

Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución.

La complejidad computacional del algoritmo se puede expresar como

El razonamiento es porque en el peor caso, cada vértice y cada arista será visitado por el algoritmo.

Cuando se sabe anteriormente el número de vértices en el grafo, y se pueden usar otras estructuras de data para determinar qué vértices han sido añadidos a la cola, la complejidad en memoria es

Especialmente con grafos muy grandes (posiblemente infinitos), puede ser más práctico describir la complejidad del algoritmo en términos del factor de ramificación.

Para encontrar los nodos que están en una distancia

de la raíz (distancia medida por el número de aristas que tiene que usar), Búsqueda en anchura requiere