Búsqueda en grafos: BFS y DFS

En 1736 Leonhard Euler demostró que ningún paseo cruza exactamente una vez cada uno de los siete puentes de Königsberg, y con esa respuesta empezó la teoría de grafos.

Puntos y líneas

Un grafo es un conjunto de puntos, llamados vértices o nodos, unidos por líneas, llamadas aristas. La idea es sencilla y sirve para muchísimas cosas: ciudades unidas por carreteras, páginas web unidas por enlaces, personas unidas por amistades, casillas de un laberinto unidas donde no hay pared. Una vez que un problema se dibuja como grafo, el mismo puñado de algoritmos puede responder preguntas como "¿puedo llegar de aquí a allá?" y "¿cuál es el camino más corto?".

Guardar un grafo en el código

Una forma común de guardar un grafo es una lista de adyacencia: para cada vértice, una lista de sus vecinos. Las notas del 6.006 del MIT usan exactamente esto, un arreglo o diccionario Adj donde Adj[u] enumera los vértices unidos a u. Para el grafo de arriba queda así:

const graph = {   // lista de adyacencia
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Búsqueda en anchura: anillo por anillo

La búsqueda en anchura (BFS) explora un grafo en anillos alrededor del inicio. Primero el propio inicio, a distancia 0. Luego todos sus vecinos, a distancia 1. Luego cada vértice nuevo junto a esos, a distancia 2, y así sucesivamente. Para hacerlo usa una cola, una fila donde el primero en entrar es el primero en salir. Toma el vértice del frente de la cola, lo visita y agrega al final sus vecinos no vistos. Desde A en el ejemplo, BFS visita A, luego B y C, luego D y E, luego F. Como avanza hacia fuera de anillo en anillo, la primera vez que BFS llega a un vértice ha encontrado un camino con el menor número de aristas. F está a 3 aristas de A, por ejemplo A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // primero en entrar, primero en salir
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Búsqueda en profundidad: todo lo lejos que puedas, y luego retroceder

La búsqueda en profundidad (DFS) se comporta como una persona en un laberinto que mantiene una mano en la pared. Sigue un camino lo más hondo posible. Cuando llega a un callejón sin salida o a un lugar que ya vio, retrocede al punto de decisión más reciente y prueba la siguiente opción. Usa una pila en lugar de una cola, último en entrar, primero en salir, y es muy natural escribirla con recursión, donde la pila de llamadas se encarga de recordar. Desde A, una DFS recursiva visita A, B, D, C, E, F. DFS llega a todos los vértices a los que llega BFS, pero el camino que sigue no es necesariamente el más corto.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // orden: A B D C E F
}

Cuál usar

En el primer laberinto del laboratorio, BFS visita 105 casillas y encuentra un camino de 22 movimientos, el más corto posible. DFS se lanza por casualidad hacia la meta y visita solo 31 casillas, pero su camino lleva 28 movimientos. Ninguna es siempre más barata. Las dos tratan cada vértice y cada arista un número fijo de veces, así que las dos se ejecutan en tiempo O(V + E) para V vértices y E aristas. Elige BFS cuando necesites el menor número de pasos: los menos movimientos en un rompecabezas, los menos enlaces entre dos personas. Elige DFS cuando necesites explorarlo todo o seguir las decisiones hasta el final: comprobar si todas las habitaciones de un laberinto están conectadas, o probar las jugadas de un rompecabezas línea por línea y retroceder al atascarte. Cuando las aristas tienen longitudes distintas, como las carreteras, ninguna basta por sí sola; métodos como el algoritmo de Dijkstra amplían la idea de BFS con distancias.