BFS y DFS

Recorrer un grafo es visitar todo lo alcanzable desde un punto sin repetir ni perderse. Hay dos formas de hacerlo, y la única diferencia entre ellas es de qué estructura se saca el próximo vértice. Ese detalle cambia por completo lo que cada recorrido puede responder.

El mismo esqueleto para los dos

El esquema es común: una estructura con los vértices pendientes y una marca de visitados. Se saca uno, se procesa y se agregan sus vecinos no visitados.

Si la estructura es una cola, el recorrido es en anchura (BFS): sale primero el que llegó primero, y el grafo se explora por capas. Si es una pila, es en profundidad (DFS): sale el último que entró, y el recorrido se hunde por una rama hasta agotarla. Con listas de adyacencia, ambos cuestan $O(V+E)$.

La trampa está en cuándo se marca

Hay una trampa en el orden de las marcas. Marcar al sacar de la cola deja entrar el mismo vértice varias veces, una por cada vecino que lo empuja, y la cola se infla.

La versión correcta marca al encolar: un vértice entra a lo sumo una vez y la cola nunca supera $V$ elementos. Esa marca también es el lugar natural para guardar de quién vino cada vértice, que es lo que después permite reconstruir el camino.

BFS: por capas, y por qué da el camino más corto

BFS visita primero todos los vértices a distancia 1, después los de distancia 2, y así. Esa disciplina por capas le da su propiedad central: la primera vez que se alcanza un vértice es por un camino con la mínima cantidad de aristas.

De ahí sale el camino más corto en grafos sin pesos, y también la distancia mínima a varios destinos en una sola pasada. Con pesos distintos deja de valer: ahí hace falta Dijkstra.

DFS: hasta el fondo y volver

DFS avanza mientras haya por dónde y retrocede cuando se queda sin vecinos nuevos. Se escribe recursivo casi solo, con la pila de llamadas haciendo de pila explícita, aunque en grafos profundos conviene la versión iterativa para no desbordarla.

Lo útil de DFS son los tiempos: cuándo entra a un vértice y cuándo termina de explorarlo. Con esos dos números salen el orden topológico —los vértices por tiempo de finalización decreciente— y las componentes fuertemente conexas.

Detectar ciclos, que depende de si es dirigido

Detectar ciclos es la aplicación clásica, y depende de si el grafo es dirigido. En uno no dirigido, encontrar un vecino ya visitado que no sea el padre inmediato indica ciclo.

En uno dirigido no alcanza: hay que distinguir un vértice ya terminado de uno que sigue abierto en la rama actual. Sólo una arista hacia un vértice todavía en exploración cierra un ciclo. Es exactamente lo que detecta un sistema de compilación cuando avisa que hay dependencias circulares.

Cuál elegir según la pregunta

La elección sigue la pregunta. Si es “qué tan lejos” o “el camino más corto en pasos”, BFS. Si es “existe un camino”, “hay ciclo”, “en qué orden se puede hacer esto”, DFS.

También difieren en memoria: BFS guarda una capa entera, que en un grafo ancho puede ser enorme; DFS guarda una rama, que en un grafo profundo puede ser igual de cara. En grafos desconectados, cualquiera de los dos hay que arrancarlo desde cada vértice no visitado para cubrir todas las componentes.

Los dos, escritos

El esqueleto es literalmente el mismo y cambia una línea: de qué punta se saca el próximo.

type Graph = ReadonlyMap<string, readonly string[]>;

const breadthFirst = (graph: Graph, start: string): string[] => {
  const visited = new Set<string>([start]);
  const pending: string[] = [start];
  const order: string[] = [];

  while (pending.length > 0) {
    const current = pending.shift()!; // del frente: FIFO
    order.push(current);

    for (const neighbour of graph.get(current) ?? []) {
      if (visited.has(neighbour)) continue;
      visited.add(neighbour); // marcar al encolar, no al desencolar
      pending.push(neighbour);
    }
  }

  return order;
};

Cambiar shift por pop convierte eso en DFS, y con eso cambian las propiedades del recorrido. La versión recursiva de DFS es más común porque la pila la pone el lenguaje:

const depthFirst = (graph: Graph, start: string, visited = new Set<string>()): string[] => {
  if (visited.has(start)) return [];
  visited.add(start);

  return [start, ...(graph.get(start) ?? []).flatMap((n) => depthFirst(graph, n, visited))];
};

Cuál de los dos, y para qué

Cierre

Cola o pila: esa es toda la diferencia. La cola da capas y caminos mínimos en aristas; la pila da profundidad, tiempos de entrada y salida, orden topológico y ciclos. Los dos recorren el grafo completo en $O(V+E)$ marcando al encolar.