Recorridos de árbol (DFS y BFS)

Recorrer un árbol

Un árbol guarda los datos en una jerarquía de nodos, pero a menudo necesitamos visitarlos todos: para buscar, sumar, imprimir o transformar. Hay dos estrategias clásicas, y la diferencia es el orden en que se visitan los nodos.

Imagina que exploras un edificio de habitaciones conectadas. Puedes meterte por un pasillo hasta el final antes de volver (profundidad), o revisar primero todas las puertas de tu planta antes de bajar a la siguiente (anchura).

DFS — Recorrido en profundidad (Depth-First Search)

DFS baja por una rama hasta el fondo antes de retroceder y probar la siguiente. Se expresa de forma muy natural con recursión: visitas el nodo y luego te llamas a ti mismo sobre cada hijo.

function dfs(nodo, visitar) {
  visitar(nodo.valor);
  for (const hijo of nodo.hijos) {
    dfs(hijo, visitar);
  }
}

La recursión usa por debajo la pila de llamadas: cada llamada espera a que terminen las de sus hijos. Por eso DFS y "pila" van de la mano.

BFS — Recorrido en anchura (Breadth-First Search)

BFS visita los nodos por niveles: primero la raíz, luego todos sus hijos, luego los nietos... Para conseguirlo se usa una cola (FIFO): metemos la raíz, y mientras la cola no esté vacía, sacamos un nodo, lo visitamos y encolamos sus hijos al final.

function bfs(raiz, visitar) {
  const cola = [raiz];
  while (cola.length > 0) {
    const nodo = cola.shift(); // saca el primero (FIFO)
    visitar(nodo.valor);
    for (const hijo of nodo.hijos) {
      cola.push(hijo); // los hijos esperan su turno al final
    }
  }
}

¿Cuál elijo?

• DFS: cuando quieres explorar caminos completos (buscar una ruta, sumar toda una rama). Más sencillo de escribir con recursión.
• BFS: cuando importa la cercanía a la raíz (el camino más corto en número de pasos, procesar nivel a nivel).

Ejemplos

DFS recursivo: visita ramas completas

const raiz = { valor: "A", hijos: [
  { valor: "B", hijos: [{ valor: "D", hijos: [] }, { valor: "E", hijos: [] }] },
  { valor: "C", hijos: [] },
]};
const orden = [];
function dfs(nodo) {
  orden.push(nodo.valor);
  for (const hijo of nodo.hijos) dfs(hijo);
}
dfs(raiz);
console.log(orden.join(" -> ")); // A -> B -> D -> E -> C

BFS con cola: visita por niveles

const raiz = { valor: "A", hijos: [
  { valor: "B", hijos: [{ valor: "D", hijos: [] }, { valor: "E", hijos: [] }] },
  { valor: "C", hijos: [] },
]};
const orden = [];
const cola = [raiz];
while (cola.length > 0) {
  const nodo = cola.shift();
  orden.push(nodo.valor);
  for (const hijo of nodo.hijos) cola.push(hijo);
}
console.log(orden.join(" -> ")); // A -> B -> C -> D -> E