Búsqueda en Anchura

La búsqueda en anchura (BFS) es uno de los algoritmos de búsqueda básicos y esenciales sobre grafos.

Como resultado de cómo funciona el algoritmo, el camino encontrado por BFS hacia cualquier nodo es el camino más corto hacia ese nodo, es decir, el camino que contiene la menor cantidad de aristas en grafos no ponderados.

El algoritmo trabaja en tiempo $O(n + m)$ , donde $n$ es la cantidad de vértices y $m$ la cantidad de aristas.

Descripción del algoritmo

El algoritmo toma como entrada un grafo no ponderado y el id del vértice fuente $s$ . El grafo de entrada puede ser dirigido o no dirigido; al algoritmo no le importa.

El algoritmo se puede entender como un fuego que se propaga sobre el grafo: en el paso cero solo la fuente $s$ está en llamas. En cada paso, el fuego que quema en cada vértice se propaga a todos sus vecinos. En una iteración del algoritmo, el “anillo de fuego” se expande en ancho una unidad (de ahí el nombre del algoritmo).

Más precisamente, el algoritmo se puede enunciar así: Crear una cola $q$ que contendrá los vértices a procesar y un arreglo booleano $used[]$ que indica, para cada vértice, si ya fue encendido (o visitado) o no.

Inicialmente, encolamos la fuente $s$ y ponemos $used[s] = true$ , y para todos los demás vértices $v$ ponemos $used[v] = false$ . Después, iteramos hasta que la cola esté vacía y en cada iteración sacamos un vértice del frente de la cola. Recorremos todas las aristas que salen de este vértice y si alguna de esas aristas va a vértices que todavía no están encendidos, los encendemos y los colocamos en la cola.

Como resultado, cuando la cola está vacía, el “anillo de fuego” contiene todos los vértices alcanzables desde la fuente $s$ , y cada vértice se alcanzó de la forma más corta posible. También se pueden calcular las longitudes de los caminos más cortos (solo hace falta mantener un arreglo de longitudes de camino $d[]$ ) y guardar información para restaurar todos esos caminos más cortos (para esto hace falta mantener un arreglo de “padres” $p[]$ , que guarda para cada vértice el vértice desde el cual lo alcanzamos).

Implementación

Escribimos código para el algoritmo descrito en C++ y Java.

=== “C++” ```cpp vector<vector> adj; // adjacency list representation int n; // number of nodes int s; // source vertex


queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int u : adj[v]) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}
```

=== “Java” ```java ArrayList<ArrayList> adj = new ArrayList<>(); // adjacency list representation


int n; // number of nodes
int s; // source vertex


LinkedList<Integer> q = new LinkedList<Integer>();
boolean used[] = new boolean[n];
int d[] = new int[n];
int p[] = new int[n];

q.push(s);
used[s] = true;
p[s] = -1;
while (!q.isEmpty()) {
    int v = q.pop();
    for (int u : adj.get(v)) {
        if (!used[u]) {
            used[u] = true;
            q.push(u);
            d[u] = d[v] + 1;
            p[u] = v;
        }
    }
}
```

Si hay que restaurar y mostrar el camino más corto de la fuente a algún vértice $u$ , se puede hacer de la siguiente manera:

=== “C++” cpp if (!used[u]) { cout << "No path!"; } else { vector<int> path; for (int v = u; v != -1; v = p[v]) path.push_back(v); reverse(path.begin(), path.end()); cout << "Path: "; for (int v : path) cout << v << " "; } === “Java” java if (!used[u]) { System.out.println("No path!"); } else { ArrayList<Integer> path = new ArrayList<Integer>(); for (int v = u; v != -1; v = p[v]) path.add(v); Collections.reverse(path); for(int v : path) System.out.println(v); }

Aplicaciones de BFS

Encontrar el camino más corto de una fuente a los demás vértices en un grafo no ponderado.
Encontrar todas las componentes conexas en un grafo no dirigido en tiempo $O(n + m)$ : Para esto, simplemente corremos BFS empezando desde cada vértice, excepto los vértices que ya fueron visitados en corridas anteriores. Así, hacemos BFS normal desde cada uno de los vértices, pero no reseteamos el arreglo $used[]$ cada vez que obtenemos una componente conexa nueva, y el tiempo total de ejecución seguirá siendo $O(n + m)$ (hacer múltiples BFS sobre el grafo sin poner a cero el arreglo $used []$ se llama una serie de búsquedas en anchura).
Encontrar una solución a un problema o a un juego con la menor cantidad de movimientos, si cada estado del juego se puede representar por un vértice del grafo, y las transiciones de un estado a otro son las aristas del grafo.
Encontrar el camino más corto en un grafo con pesos 0 o 1: Esto requiere solo una pequeña modificación al BFS normal: en lugar de mantener el arreglo $used[]$ , ahora chequeamos si la distancia al vértice es menor que la distancia encontrada actualmente; entonces, si la arista actual tiene peso cero, la agregamos al frente de la cola; si no, al final de la cola. Esta modificación se explica con más detalle en el artículo BFS 0-1.
Encontrar el ciclo más corto en un grafo dirigido no ponderado: Empezar una búsqueda en anchura desde cada vértice. En cuanto intentemos ir del vértice actual de vuelta al vértice fuente, encontramos el ciclo más corto que contiene al vértice fuente. En ese punto podemos detener el BFS y empezar un BFS nuevo desde el siguiente vértice. De todos esos ciclos (a lo sumo uno por cada BFS) elegir el más corto.
Encontrar todas las aristas que yacen en algún camino más corto entre un par dado de vértices $(a, b)$ . Para esto, correr dos búsquedas en anchura: una desde $a$ y una desde $b$ . Sea $d_a []$ el arreglo con las distancias más cortas obtenidas del primer BFS (desde $a$ ) y $d_b []$ el arreglo con las distancias más cortas obtenidas del segundo BFS desde $b$ . Ahora, para cada arista $(u, v)$ es fácil chequear si esa arista yace en algún camino más corto entre $a$ y $b$ : el criterio es la condición $d_a [u] + 1 + d_b [v] = d_a [b]$ .
Encontrar todos los vértices en algún camino más corto entre un par dado de vértices $(a, b)$ . Para eso, correr dos búsquedas en anchura: una desde $a$ y una desde $b$ . Sea $d_a []$ el arreglo con las distancias más cortas obtenidas del primer BFS (desde $a$ ) y $d_b []$ el arreglo con las distancias más cortas obtenidas del segundo BFS (desde $b$ ). Ahora, para cada vértice es fácil chequear si yace en algún camino más corto entre $a$ y $b$ : el criterio es la condición $d_a [v] + d_b [v] = d_a [b]$ .
Encontrar el walk más corto de longitud par de un vértice fuente $s$ a un vértice objetivo $t$ en un grafo no ponderado: Para esto, hay que construir un grafo auxiliar cuyos vértices son el estado $(v, c)$ , donde $v$ es el nodo actual, $c = 0$ o $c = 1$ es la paridad actual. Cualquier arista $(u, v)$ del grafo original en esta nueva columna se convierte en dos aristas $((u, 0), (v, 1))$ y $((u, 1), (v, 0))$ . Después corremos un BFS para encontrar el walk más corto del vértice de inicio $(s, 0)$ al vértice final $(t, 0)$ .
Nota: Este ítem usa el término “walk” en lugar de “path” a propósito, porque los vértices pueden potencialmente repetirse en el walk encontrado para que su longitud sea par. El problema de encontrar el path más corto de longitud par es NP-completo en grafos dirigidos, y resoluble en tiempo lineal en grafos no dirigidos, pero con un enfoque mucho más involucrado.

Búsqueda en Anchura

Descripción del algoritmo

Implementación

Aplicaciones de BFS

Problemas de práctica