¿Qué es el algoritmo de búsqueda en anchura?

El algoritmo de búsqueda en anchura (BFS - Breadth-First Search) es un algoritmo de recorrido o búsqueda en un árbol o grafo. Comienza desde el nodo raíz (o un nodo arbitrario si el grafo no es un árbol) y explora todos sus vecinos inmediatos, luego explora los vecinos de estos vecinos, y así sucesivamente, nivel por nivel. BFS se implementa usando una cola.

Principio de funcionamiento:

1. Coloca el nodo inicial en la cola.
2. Mientras la cola no esté vacía:
   • Extrae un nodo de la cola.
   • Si el nodo es el buscado, detiene la búsqueda.
   • De lo contrario, coloca en la cola todos sus vecinos no visitados y márcalos como visitados.

Características:

• Completitud: Garantiza encontrar una solución si existe.
• Óptimalidad: Encuentra el camino más corto en un grafo sin peso (donde los pesos de las aristas son iguales).
• Complejidad en tiempo: Depende de la estructura del grafo, para E aristas y V vértices — O(V + E).
• Complejidad en memoria: O(V) en el peor caso, ya que se deben almacenar los vértices visitados y la cola.

Aplicaciones en QA:

• Búsqueda del camino más corto entre nodos en escenarios de prueba.
• Exploración de todos los estados alcanzables del sistema durante pruebas de autómatas finitos.
• Pruebas de accesibilidad de todas las páginas de un sitio web mediante crawling.

Ejemplo (recorrido de árbol):

from collections import deque

# Ejemplo de representación de árbol en forma de diccionario de adyacencia
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Ejemplo de llamada
# bfs(graph, 'A')
# Salida:
# A
# B
# C
# D
# E
# F