Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 25/32

Recorrer un grafo: BFS y DFS

✕
1/8

BFS: por capas, con una cola

La búsqueda en anchura (BFS, *breadth-first search*) visita primero a los vecinos del origen, luego a los vecinos de esos, y así, como las ondas de una piedra en el agua. Usa una cola: el que se descubre primero se visita primero.

Como avanza por capas, la primera vez que llega a un vértice lo hace por el camino con menos aristas. Por eso BFS da la distancia en saltos desde el origen. Lo único que hay que cuidar es no meter a nadie dos veces: se marca al descubrirlo.

Cuesta O(V + E): cada vértice entra una vez y cada arista se mira una vez por punta.

ABCDEF
leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

  • Primero A, luego su capa (B y C), luego la siguiente (D y E) y al final F.
  • F queda a 3 saltos: A → B → D → F o A → C → E → F, cualquiera de los dos.
  • El arreglo cola nunca se vacía: al final es el orden en que se visitó todo.
Toda la lección en una página

BFS: por capas, con una cola

La búsqueda en anchura (BFS, *breadth-first search*) visita primero a los vecinos del origen, luego a los vecinos de esos, y así, como las ondas de una piedra en el agua. Usa una cola: el que se descubre primero se visita primero.

Como avanza por capas, la primera vez que llega a un vértice lo hace por el camino con menos aristas. Por eso BFS da la distancia en saltos desde el origen. Lo único que hay que cuidar es no meter a nadie dos veces: se marca al descubrirlo.

Cuesta O(V + E): cada vértice entra una vez y cada arista se mira una vez por punta.

ABCDEF
const ady = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

function bfs(inicio) {
  const dist = { [inicio]: 0 };   // descubierto = ya tiene distancia
  const cola = [inicio];
  let cabeza = 0;                  // sacar con un índice: shift() es O(n)
  while (cabeza < cola.length) {
    const v = cola[cabeza++];
    for (const w of ady[v]) {
      if (!(w in dist)) {
        dist[w] = dist[v] + 1;
        cola.push(w);
      }
    }
  }
  console.log("orden de visita:", cola);
  return dist;
}

console.log(bfs("A"));
  • Primero A, luego su capa (B y C), luego la siguiente (D y E) y al final F.
  • F queda a 3 saltos: A → B → D → F o A → C → E → F, cualquiera de los dos.
  • El arreglo cola nunca se vacía: al final es el orden en que se visitó todo.

DFS: hasta el fondo, y de regreso

La búsqueda en profundidad (DFS, *depth-first search*) se mete por un camino hasta que ya no puede seguir y luego regresa a probar el siguiente. Es el recorrido en preorden de los árboles, pero marcando lo visitado, porque en un grafo hay ciclos y se daría vueltas para siempre.

Se escribe con recursión (la pila de llamadas hace el trabajo) o con una pila explícita. No da distancias, pero sirve para todo lo que es «¿qué se alcanza desde aquí?». Por ejemplo, contar componentes: los pedazos sueltos del grafo. Cada DFS que arranca en un vértice no visitado descubre un componente entero.

const ady = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

const visto = new Set();
const orden = [];
function dfs(v) {
  visto.add(v);
  orden.push(v);
  for (const w of ady[v]) if (!visto.has(w)) dfs(w);
}
dfs("A");
console.log("DFS desde A:", orden);

// Tres pedazos: P-Q-R, S-T y U solo
const red = { P: ["Q"], Q: ["P", "R"], R: ["Q"], S: ["T"], T: ["S"], U: [] };

function componentes(g) {
  const visto = new Set();
  let cuenta = 0;
  for (const inicio in g) {
    if (visto.has(inicio)) continue;
    cuenta++;                      // nadie lo alcanzó: pedazo nuevo
    const pila = [inicio];         // DFS con pila explícita
    visto.add(inicio);
    while (pila.length > 0) {
      const v = pila.pop();
      for (const w of g[v]) if (!visto.has(w)) { visto.add(w); pila.push(w); }
    }
  }
  return cuenta;
}
console.log("componentes:", componentes(red));
  • DFS desde A va A → B → D → C → E → F: se mete por B hasta el fondo antes de tocar a C como vecino de A. BFS, en cambio, visitó B y C juntos.
  • red tiene 3 componentes; U solo cuenta como uno.

Un mapa también es un grafo

Una rejilla (un tablero, un mapa de casillas) es un grafo aunque nadie lo dibuje así: cada casilla es un vértice y sus vecinas de arriba, abajo, izquierda y derecha son sus aristas. No hace falta armar la lista de adyacencia: los vecinos se calculan sumando [1, 0], [-1, 0], [0, 1] y [0, -1].

El problema clásico es contar islas: en un mapa de 1 (tierra) y 0 (agua), cuántos grupos de tierra hay. Son los componentes del grafo de la tierra. El Snake de Daily Challenge hace algo parecido para revisar que un muro nuevo no parta la arena en dos.

1100011010000110000001100
  • 0 agua
  • 1 tierra
const mapa = [
  "11000",
  "11010",
  "00011",
  "00000",
  "01100",
];

function contarIslas(mapa) {
  const filas = mapa.length, cols = mapa[0].length;
  const visto = mapa.map(() => new Array(cols).fill(false));
  let islas = 0;
  for (let y = 0; y < filas; y++) {
    for (let x = 0; x < cols; x++) {
      if (mapa[y][x] !== "1" || visto[y][x]) continue;
      islas++;                                 // tierra que nadie visitó
      const cola = [[y, x]];                   // BFS desde aquí
      visto[y][x] = true;
      let cabeza = 0;
      while (cabeza < cola.length) {
        const [cy, cx] = cola[cabeza++];
        for (const [dy, dx] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
          const ny = cy + dy, nx = cx + dx;
          if (ny < 0 || ny >= filas || nx < 0 || nx >= cols) continue;
          if (mapa[ny][nx] === "1" && !visto[ny][nx]) {
            visto[ny][nx] = true;
            cola.push([ny, nx]);
          }
        }
      }
    }
  }
  return islas;
}

console.log(contarIslas(mapa));

Salen 3: el cuadro de arriba a la izquierda, la «L» de la derecha (las casillas en diagonal no cuentan como vecinas, pero ésas se tocan de lado) y la de abajo. Cambia un 0 del mapa por 1 para unir dos islas y córrelo.

Practica con un reto en vídeo