Algoritmos de búsqueda en anchura (BFS)

8.1 Principios de funcionamiento del algoritmo BFS

Búsqueda en anchura (Breadth-First Search, BFS) — es un algoritmo de recorrido o búsqueda en un grafo que comienza desde un vértice inicial y explora todos sus vértices adyacentes en el nivel actual antes de pasar a los vértices del siguiente nivel.

Pasos del algoritmo:

1. Comienza con el vértice inicial elegido y colócalo en la cola.
2. Mientras la cola no esté vacía, realiza las siguientes acciones:
   • Extrae el vértice de la cabeza de la cola y márcalo como visitado.
   • Para cada vértice adyacente no visitado, agrégalo a la cola.
3. Repite el paso 2 hasta que se visiten todos los vértices alcanzables desde el vértice inicial.

Visualización:

Complejidad temporal:

O(V + E), donde V — cantidad de vértices, E — cantidad de aristas.

Cada nodo y cada arista del grafo se visitan una vez.

Complejidad espacial:

O(V), ya que se utiliza una cola para almacenar los vértices, así como matrices para almacenar el estado (vértices visitados).

8.2 Implementación de BFS usando una cola

La búsqueda en anchura se implementa bien con una estructura de datos como una cola.

Implementación de BFS usando una cola:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Procesamiento del nodo
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# Ejemplo de uso:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 Búsqueda bidireccional en anchura

BFS se usa a menudo en juegos cuando es necesario encontrar el camino más corto entre dos puntos en un terreno complicado. Este problema se convierte fácilmente en un problema de búsqueda de caminos en un grafo entre dos vértices. Las aristas de dicho grafo son todos los caminos transitables en el mapa.

Pero para encontrar un camino más rápido, generalmente se busca desde ambos extremos. Para esto se aplica BFS bidireccional.

Principio de funcionamiento

La búsqueda bidireccional en anchura (Bidirectional BFS) es una variante optimizada del algoritmo BFS, que realiza dos travesías paralelas del grafo: una desde el vértice inicial y otra desde el vértice objetivo. Las travesías continúan hasta que los dos recorridos se encuentren, lo que reduce significativamente la cantidad de vértices y aristas revisadas en comparación con el BFS clásico.

Pasos del algoritmo:

• Inicializar dos colas: una para el recorrido desde el vértice inicial, la otra desde el objetivo.
• Inicializar dos conjuntos de vértices visitados para rastrear los vértices visitados en ambas direcciones.
• Realizar el recorrido alternativo del grafo desde ambas colas.
• En cada paso se verifica si los conjuntos de vértices visitados se intersectan. Si se encuentra una intersección, el camino existe.
• El proceso continúa hasta que se encuentre un nodo intersectante o las colas se vacíen.

Complejidad temporal

En el mejor caso: O(2 * (V + E)) = O(V + E), donde V — cantidad de vértices, E — cantidad de aristas.

El BFS bidireccional generalmente realiza el recorrido de un menor número de vértices en comparación con el BFS de un solo paso, especialmente en grafos grandes.

Complejidad espacial:

O(V) para almacenar dos colas y dos conjuntos de vértices visitados.

Ejemplo de implementación de BFS bidireccional

El ejemplo es muy largo, el algoritmo es tres veces más largo que la búsqueda unidireccional, por lo que no lo presentaré. Cuando realmente lo necesites, podrás escribirlo por ti mismo.

8.4 Ejemplos de problemas resueltos usando BFS

Ejemplos clásicos de problemas resueltos usando BFS:

1. Búsqueda del camino más corto en un grafo no dirigido:

BFS se usa para encontrar el camino más corto (el menor número de aristas) desde el vértice inicial al objetivo en un grafo no dirigido.

Aplicación:

• En sistemas de navegación para encontrar el camino más corto entre puntos.
• En análisis de redes para encontrar el camino más corto para la transmisión de datos.

2. Verificación de la conectividad del grafo:

Verificar si el grafo es conexo, es decir, si existe un camino entre dos vértices cualesquiera.

Aplicación:

• En análisis de redes para verificar la conectividad de la red.
• En análisis de redes sociales para verificar la conectividad del grupo de usuarios.

3. Generación de laberintos:

Uso de BFS para generar laberintos aleatorios con propiedades dadas.

Aplicación:

• En aplicaciones de juego para crear laberintos.
• En robótica para probar algoritmos de navegación.

4. Búsqueda en anchura en árboles:

BFS se usa para recorrer árboles, para realizar acciones en cada nivel del árbol (por ejemplo, imprimir todos los nodos en cada nivel).

Aplicación:

• En problemas de visualización de datos, donde se requiere mostrar datos por niveles.
• En problemas de planificación, donde se requiere realizar acciones en cada nivel de jerarquía.

5. Verificación de la bipartitividad del grafo:

Verificar si el grafo es bipartito, es decir, si sus vértices se pueden dividir en dos conjuntos de manera que las aristas existan solo entre vértices de distintos conjuntos.

Aplicación:

• En teoría de grafos para verificar la bipartitividad del grafo.
• En problemas de coloración de grafos, donde es necesario verificar si se puede colorear el grafo con dos colores.