Grafos: DFS y BFS

Los grafos son la estructura de datos más general: representan cualquier cosa con conexiones entre entidades. Las redes sociales son grafos (personas = nodos, amistades = aristas). Los mapas son grafos (ciudades = nodos, carreteras = aristas). Internet es un grafo (servidores = nodos, cables = aristas).

Un grafo puede ser dirigido (las aristas tienen dirección, como seguir a alguien en Twitter) o no dirigido (como una amistad en Facebook que es mutua).

DFS en grafos usa recursión o un Stack explícito para explorar todos los nodos alcanzables desde un punto, marcando los visitados para evitar ciclos. Detecta componentes conectados, ciclos, y orden topológico (para dependencias: en qué orden instalar paquetes de software). BFS en grafos usa una Queue y encuentra el camino con menos aristas entre dos nodos.

Para grafos con pesos (distancias en un mapa), Dijkstra es la versión "pesada" de BFS que encuentra el camino más corto en O((V+E) log V).

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

// DFS iterativo
function dfs(grafo, inicio) {
  const visitados = new Set();
  const pila = [inicio];
  const orden = [];
  
  while (pila.length > 0) {
    const nodo = pila.pop();
    if (!visitados.has(nodo)) {
      visitados.add(nodo);
      orden.push(nodo);
      for (const vecino of grafo[nodo]) {
        if (!visitados.has(vecino)) pila.push(vecino);
      }
    }
  }
  return orden;
}

// BFS - camino más corto en grafos sin pesos
function bfsCamino(grafo, inicio, fin) {
  const cola = [[inicio, [inicio]]];
  const visitados = new Set([inicio]);
  
  while (cola.length > 0) {
    const [nodo, camino] = cola.shift();
    if (nodo === fin) return camino;
    
    for (const vecino of grafo[nodo]) {
      if (!visitados.has(vecino)) {
        visitados.add(vecino);
        cola.push([vecino, [...camino, vecino]]);
      }
    }
  }
  return null; // No hay camino
}

// Número de islas (problema muy común)
function numIslas(grid) {
  let islas = 0;
  
  function dfsMarca(i, j) {
    if (i < 0 || i >= grid.length || j < 0 ||
        j >= grid[0].length || grid[i][j] === "0") return;
    grid[i][j] = "0"; // Marcar como visitado
    dfsMarca(i+1, j); dfsMarca(i-1, j);
    dfsMarca(i, j+1); dfsMarca(i, j-1);
  }
  
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        islas++;
        dfsMarca(i, j);
      }
    }
  }
  return islas;
}